Given an array of digits of length n > 1, digits lies within range 0 to 9. We perform sequence of below three operations until we are done with all digits
Ā
- Select starting two digits and add ( + )
- Then next digit is subtracted ( ā ) from result of above step.Ā
Ā - The result of above step is multiplied ( X ) with next digit.
We perform above sequence of operations linearly with remaining digits.Ā
The task is to find how many permutations of given array that produce positive result after above operations.
For Example, consider input number[] = {1, 2, 3, 4, 5}. Let us consider a permutation 21345 to demonstrate sequence of operations.Ā
- Add first two digits, result = 2+1 = 3
- Subtract next digit, result=result-3= 3-3 = 0
- Multiply next digit, result=result*4= 0*4 = 0
- Add next digit, result = result+5 = 0+5 = 5
- result = 5 which is positive so increment count by one
Examples:Ā
Ā
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 )
Asked in : Morgan Stanley
Ā
We first generate all possible permutations of given digit array and perform given sequence of operations sequentially on each permutation and check for which permutation result is positive. Below code describes problem solution easily.
Note : We can generate all possible permutations either by using iterative method, see this article or we can use STL function next_permutation() function to generate it.Ā
Ā
C++
// C++ program to find count of permutations that produce// positive result.#include<bits/stdc++.h>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 nint 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 caseint 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 Codepublic 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 Codeif __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 Codestatic 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> |
Output:Ā
4
Time Complexity: O(n*n!)
Auxiliary Space: O(1)
If you have better and optimized solution for this problem then please share in comments.
If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.uk or mail your article to review-team@neveropen.co.uk. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ā
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
