Pozitif sonuç üreten permütasyonları sayın
Uzunluğu n > 1 olan bir rakam dizisi verildiğinde, 0 ile 9 arasında bir rakam yer alır. Tüm rakamlarla işimiz bitene kadar aşağıdaki üç işlemi gerçekleştiririz.
- Başlangıç iki rakamını seçin ve ( + ) ekleyin
- Daha sonra bir sonraki rakam yukarıdaki adımın sonucundan (-) çıkarılır.
- Yukarıdaki adımın sonucu ( X ) bir sonraki rakamla çarpılır.
Yukarıdaki işlem dizisini kalan rakamlarla doğrusal olarak gerçekleştiriyoruz.
Görev, yukarıdaki işlemlerden sonra verilen dizinin kaç permütasyonunun pozitif sonuç ürettiğini bulmaktır.
Örneğin giriş numarasını[] = {1 2 3 4 5} olarak düşünün. İşlem sırasını göstermek için 21345 permütasyonunu ele alalım.
- İlk iki rakamı ekle sonuç = 2+1 = 3
- Sonraki rakamı çıkar sonuç=sonuç-3= 3-3 = 0
- Sonraki rakamı çarp sonuç=sonuç*4= 0*4 = 0
- Sonraki rakamı ekle sonuç = sonuç+5 = 0+5 = 5
- sonuç = 5 pozitiftir, dolayısıyla sayımı birer birer artırın
Örnekler:
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 )
Şurada soruldu: Morgan Stanley
Öncelikle verilen rakam dizisinin tüm olası permütasyonlarını üretiriz ve her permütasyonda verilen işlem dizisini sırayla gerçekleştiririz ve hangi permütasyon sonucunun pozitif olduğunu kontrol ederiz. Aşağıdaki kod problem çözümünü kolayca açıklamaktadır.
Not : Tüm olası permütasyonları yinelemeli yöntemi kullanarak üretebiliriz (bkz. Bu makale veya STL işlevini kullanabiliriz sonraki_permütasyon() oluşturma işlevini yerine getirir.
// 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>
Çıkış:
4
Zaman Karmaşıklığı: O(n*n!)
Yardımcı Alan: O(1)
Bu sorun için daha iyi ve optimize edilmiş bir çözümünüz varsa lütfen yorumlarınızı paylaşın.
