Count permutations that produce positive result - GeeksforGeeks
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
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.
Read full article from Count permutations that produce positive result - GeeksforGeeks
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.
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
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;
}