Brojite permutacije koje daju pozitivan rezultat
Zadano je polje znamenki duljine n > 1 znamenki nalazi se unutar raspona od 0 do 9. Izvodimo niz od ispod tri operacije dok ne završimo sa svim znamenkama
- Odaberite početne dvije znamenke i dodajte ( + )
- Zatim se sljedeća znamenka oduzima (-) od rezultata gornjeg koraka.
- Rezultat gornjeg koraka se množi (X) sa sljedećom znamenkom.
Gornji niz operacija izvodimo linearno s preostalim znamenkama.
Zadatak je pronaći koliko permutacija zadanog niza daje pozitivan rezultat nakon gornjih operacija.
Na primjer, razmotrite ulazni broj [] = {1 2 3 4 5}. Razmotrimo permutaciju 21345 da demonstriramo redoslijed operacija.
- Zbrojite prve dvije znamenke rezultat = 2+1 = 3
- Oduzmite sljedeću znamenku rezultat=rezultat-3= 3-3 = 0
- Pomnožite sljedeću znamenku rezultat=rezultat*4= 0*4 = 0
- Dodajte sljedeću znamenku rezultat = rezultat+5 = 0+5 = 5
- rezultat = 5 što je pozitivno pa povećavaj broj za jedan
Primjeri:
Input : number[]='123' Output: 4 // here we have all permutations // 123 --> 1+2 -> 3-3 -> 0 // 132 --> 1+3 -> 4-2 -> 2 ( positive ) // 213 --> 2+1 -> 3-3 -> 0 // 231 --> 2+3 -> 5-1 -> 4 ( positive ) // 312 --> 3+1 -> 4-2 -> 2 ( positive ) // 321 --> 3+2 -> 5-1 -> 4 ( positive ) // total 4 permutations are giving positive result Input : number[]='112' Output: 2 // here we have all permutations possible // 112 --> 1+1 -> 2-2 -> 0 // 121 --> 1+2 -> 3-1 -> 2 ( positive ) // 211 --> 2+1 -> 3-1 -> 2 ( positive )
Pitano u: Morgan Stanley
Prvo generiramo sve moguće permutacije zadanog niza znamenki i izvodimo zadani niz operacija uzastopno na svakoj permutaciji i provjeravamo koji je rezultat permutacije pozitivan. Donji kod lako opisuje rješenje problema.
Napomena: Možemo generirati sve moguće permutacije korištenjem iterativne metode vidi ovaj članak ili možemo koristiti STL funkciju sljedeća_permutacija() funkciju za njegovo generiranje.
// C++ program to find count of permutations that produce // positive result. #include using namespace std ; // function to find all permutation after executing given // sequence of operations and whose result value is positive // result > 0 ) number[] is array of digits of length of n int countPositivePermutations ( int number [] int n ) { // First sort the array so that we get all permutations // one by one using next_permutation. sort ( number number + n ); // Initialize result (count of permutations with positive // result) int count = 0 ; // Iterate for all permutation possible and do operation // sequentially in each permutation do { // Stores result for current permutation. First we // have to select first two digits and add them int curr_result = number [ 0 ] + number [ 1 ]; // flag that tells what operation we are going to // perform // operation = 0 ---> addition operation ( + ) // operation = 1 ---> subtraction operation ( - ) // operation = 0 ---> multiplication operation ( X ) // first sort the array of digits to generate all // permutation in sorted manner int operation = 1 ; // traverse all digits for ( int i = 2 ; i < n ; i ++ ) { // sequentially perform + - X operation switch ( operation ) { case 0 : curr_result += number [ i ]; break ; case 1 : curr_result -= number [ i ]; break ; case 2 : curr_result *= number [ i ]; break ; } // next operation (decides case of switch) operation = ( operation + 1 ) % 3 ; } // result is positive then increment count by one if ( curr_result > 0 ) count ++ ; // generate next greater permutation until it is // possible } while ( next_permutation ( number number + n )); return count ; } // Driver program to test the case int main () { int number [] = { 1 2 3 }; int n = sizeof ( number ) / sizeof ( number [ 0 ]); cout < < countPositivePermutations ( number n ); return 0 ; }
Java // Java program to find count of permutations // that produce positive result. import java.util.* ; class GFG { // function to find all permutation after // executing given sequence of operations // and whose result value is positive result > 0 ) // number[] is array of digits of length of n static int countPositivePermutations ( int number [] int n ) { // First sort the array so that we get // all permutations one by one using // next_permutation. Arrays . sort ( number ); // Initialize result (count of permutations // with positive result) int count = 0 ; // Iterate for all permutation possible and // do operation sequentially in each permutation do { // Stores result for current permutation. // First we have to select first two digits // and add them int curr_result = number [ 0 ] + number [ 1 ] ; // flag that tells what operation we are going to // perform // operation = 0 ---> addition operation ( + ) // operation = 1 ---> subtraction operation ( - ) // operation = 0 ---> multiplication operation ( X ) // first sort the array of digits to generate all // permutation in sorted manner int operation = 1 ; // traverse all digits for ( int i = 2 ; i < n ; i ++ ) { // sequentially perform + - X operation switch ( operation ) { case 0 : curr_result += number [ i ] ; break ; case 1 : curr_result -= number [ i ] ; break ; case 2 : curr_result *= number [ i ] ; break ; } // next operation (decides case of switch) operation = ( operation + 1 ) % 3 ; } // result is positive then increment count by one if ( curr_result > 0 ) count ++ ; // generate next greater permutation until // it is possible } while ( next_permutation ( number )); return count ; } static boolean next_permutation ( int [] p ) { for ( int a = p . length - 2 ; a >= 0 ; -- a ) if ( p [ a ] < p [ a + 1 ] ) for ( int b = p . length - 1 ;; -- b ) if ( p [ b ] > p [ a ] ) { int t = p [ a ] ; p [ a ] = p [ b ] ; p [ b ] = t ; for ( ++ a b = p . length - 1 ; a < b ; ++ a -- b ) { t = p [ a ] ; p [ a ] = p [ b ] ; p [ b ] = t ; } return true ; } return false ; } // Driver Code public static void main ( String [] args ) { int number [] = { 1 2 3 }; int n = number . length ; System . out . println ( countPositivePermutations ( number n )); } } // This code is contributed by PrinciRaj1992
Python3 # Python3 program to find count of permutations # that produce positive result. # function to find all permutation after # executing given sequence of operations # and whose result value is positive result > 0 ) # number[] is array of digits of length of n def countPositivePermutations ( number n ): # First sort the array so that we get # all permutations one by one using # next_permutation. number . sort () # Initialize result (count of permutations # with positive result) count = 0 ; # Iterate for all permutation possible and # do operation sequentially in each permutation while True : # Stores result for current permutation. # First we have to select first two digits # and add them curr_result = number [ 0 ] + number [ 1 ]; # flag that tells what operation we are going to # perform # operation = 0 ---> addition operation ( + ) # operation = 1 ---> subtraction operation ( - ) # operation = 0 ---> multiplication operation ( X ) # first sort the array of digits to generate all # permutation in sorted manner operation = 1 ; # traverse all digits for i in range ( 2 n ): # sequentially perform + - X operation if operation == 0 : curr_result += number [ i ]; else if operation == 1 : curr_result -= number [ i ]; else if operation == 2 : curr_result *= number [ i ]; # next operation (decides case of switch) operation = ( operation + 1 ) % 3 ; # result is positive then increment count by one if ( curr_result > 0 ): count += 1 # generate next greater permutation until # it is possible if ( not next_permutation ( number )): break return count ; def next_permutation ( p ): for a in range ( len ( p ) - 2 - 1 - 1 ): if ( p [ a ] < p [ a + 1 ]): for b in range ( len ( p ) - 1 - 1000000000 - 1 ): if ( p [ b ] > p [ a ]): t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; a += 1 b = len ( p ) - 1 while ( a < b ): t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; a += 1 b -= 1 return True ; return False ; # Driver Code if __name__ == '__main__' : number = [ 1 2 3 ] n = len ( number ) print ( countPositivePermutations ( number n )); # This code is contributed by rutvik_56.
C# // C# program to find count of permutations // that produce positive result. using System ; class GFG { // function to find all permutation after // executing given sequence of operations // and whose result value is positive result > 0 ) // number[] is array of digits of length of n static int countPositivePermutations ( int [] number int n ) { // First sort the array so that we get // all permutations one by one using // next_permutation. Array . Sort ( number ); // Initialize result (count of permutations // with positive result) int count = 0 ; // Iterate for all permutation possible and // do operation sequentially in each permutation do { // Stores result for current permutation. // First we have to select first two digits // and add them int curr_result = number [ 0 ] + number [ 1 ]; // flag that tells what operation we are going to // perform // operation = 0 ---> addition operation ( + ) // operation = 1 ---> subtraction operation ( - ) // operation = 0 ---> multiplication operation ( X ) // first sort the array of digits to generate all // permutation in sorted manner int operation = 1 ; // traverse all digits for ( int i = 2 ; i < n ; i ++ ) { // sequentially perform + - X operation switch ( operation ) { case 0 : curr_result += number [ i ]; break ; case 1 : curr_result -= number [ i ]; break ; case 2 : curr_result *= number [ i ]; break ; } // next operation (decides case of switch) operation = ( operation + 1 ) % 3 ; } // result is positive then increment count by one if ( curr_result > 0 ) count ++ ; // generate next greater permutation until // it is possible } while ( next_permutation ( number )); return count ; } static bool next_permutation ( int [] p ) { for ( int a = p . Length - 2 ; a >= 0 ; -- a ) if ( p [ a ] < p [ a + 1 ]) for ( int b = p . Length - 1 ;; -- b ) if ( p [ b ] > p [ a ]) { int t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; for ( ++ a b = p . Length - 1 ; a < b ; ++ a -- b ) { t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; } return true ; } return false ; } // Driver Code static public void Main () { int [] number = { 1 2 3 }; int n = number . Length ; Console . Write ( countPositivePermutations ( number n )); } } // This code is contributed by ajit..
JavaScript < script > // Javascript program to find count of permutations // that produce positive result. // function to find all permutation after // executing given sequence of operations // and whose result value is positive result > 0 ) // number[] is array of digits of length of n function countPositivePermutations ( number n ) { // First sort the array so that we get // all permutations one by one using // next_permutation. number . sort ( function ( a b ){ return a - b }); // Initialize result (count of permutations // with positive result) let count = 0 ; // Iterate for all permutation possible and // do operation sequentially in each permutation do { // Stores result for current permutation. // First we have to select first two digits // and add them let curr_result = number [ 0 ] + number [ 1 ]; // flag that tells what operation we are going to // perform // operation = 0 ---> addition operation ( + ) // operation = 1 ---> subtraction operation ( - ) // operation = 0 ---> multiplication operation ( X ) // first sort the array of digits to generate all // permutation in sorted manner let operation = 1 ; // traverse all digits for ( let i = 2 ; i < n ; i ++ ) { // sequentially perform + - X operation switch ( operation ) { case 0 : curr_result += number [ i ]; break ; case 1 : curr_result -= number [ i ]; break ; case 2 : curr_result *= number [ i ]; break ; } // next operation (decides case of switch) operation = ( operation + 1 ) % 3 ; } // result is positive then increment count by one if ( curr_result > 0 ) count ++ ; // generate next greater permutation until // it is possible } while ( next_permutation ( number )); return count ; } function next_permutation ( p ) { for ( let a = p . length - 2 ; a >= 0 ; -- a ) if ( p [ a ] < p [ a + 1 ]) for ( let b = p . length - 1 ;; -- b ) if ( p [ b ] > p [ a ]) { let t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; for ( ++ a b = p . length - 1 ; a < b ; ++ a -- b ) { t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; } return true ; } return false ; } let number = [ 1 2 3 ]; let n = number . length ; document . write ( countPositivePermutations ( number n )); < /script>
Izlaz:
4
Vremenska složenost: O(n*n!)
Pomoćni prostor: O(1)
Ako imate bolje i optimizirano rješenje za ovaj problem, podijelite ga u komentarima.
