n > 1 숫자 길이의 숫자 배열이 0에서 9 사이에 있다고 가정합니다. 우리는 모든 숫자가 완료될 때까지 아래 세 가지 작업을 순서대로 수행합니다.
- 시작하는 두 자리 숫자를 선택하고 ( + )를 추가하세요.
- 그런 다음 위 단계의 결과에서 다음 숫자를 뺍니다( - ).
- 위 단계의 결과에 다음 숫자를 곱합니다( X ).
나머지 숫자를 사용하여 위의 일련의 작업을 선형으로 수행합니다.
작업은 위의 작업 후에 긍정적인 결과를 생성하는 주어진 배열의 순열 수를 찾는 것입니다.
예를 들어 입력 번호[] = {1 2 3 4 5}를 고려하십시오. 연산 순서를 보여주기 위해 순열 21345를 고려해 보겠습니다.
- 처음 두 자리 더하기 결과 = 2+1 = 3
- 다음 숫자 빼기 결과=결과-3= 3-3 = 0
- 다음 숫자 곱하기 결과=결과*4= 0*4 = 0
- 다음 숫자 추가 결과 = 결과+5 = 0+5 = 5
- 결과 = 5는 양수이므로 1씩 증가합니다.
예:
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 )
질문 위치: 모건스탠리
먼저 주어진 숫자 배열의 가능한 모든 순열을 생성하고 각 순열에 대해 주어진 일련의 작업을 순차적으로 수행하고 어떤 순열 결과가 긍정적인지 확인합니다. 아래 코드는 문제 해결 방법을 쉽게 설명합니다.
메모 : 반복 방법을 사용하여 가능한 모든 순열을 생성할 수 있습니다. 이것 기사 또는 STL 기능을 사용할 수 있습니다 다음_순열() 생성하는 함수입니다.
C++
// C++ program to find count of permutations that produce // positive result. #include
// 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 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# 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..
<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>
산출:
4
시간 복잡도: O(n*n!)
보조 공간: O(1)
이 문제에 대해 더 좋고 최적화된 솔루션이 있다면 댓글로 공유해 주세요.