Last Updated: 15 Oct, 2021
Reduce Array
Moderate
Asked in companies
Ninja was solving questions on the array where he came across a question in which Ninja has an array ‘ARR’ of ‘N’ integers in which he has to perform the following operations to get the result.
1- In one successful operation, Ninja can remove two positive integers, ‘A’ and ‘B’, and insert their sum, i.e., ‘A’ + ‘B’ into the position of either ‘A’ or ‘B’.
2- To insert sum in the position of element ‘A’, the condition 2 * ’A’ >= ‘B’ should be satisfied. Similarly, to insert the sum in the position of element ‘B’, the condition 2 * ‘B’ >= A should be satisfied.
3- We will insert the sum at one position, and the value at the other position should be changed to -1.
4- The resultant array should contain only 1 positive element.
Your task is to find the count of distinct combinations possible for the array.
Note:
A combination is different if they lead to a different position of the element that remains positive at the end of all successful operations for that combination.
For example:
Let ‘ARR’ be: {2, 1}
Combination 1:
Pick 2 and 1 and insert their sum at the position of 2: [3, -1]
Combination 2:
Pick 2 and 1 and insert their sum at the position of 1: [-1, 3]
So total combinations are 2.
Input Format :
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains a single integer ‘N’, representing the size of the array.
The second line of each test case contains ‘N’ space-separated integers, representing the array ‘ARR’ elements.
Output Format :
For each test case, print a single integer representing the count of distinct combinations possible for the array.
Print output of each test case in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
Approaches
The basic idea is to sort the array and then use the prefix sum to find the count of distinct combinations. We sort the array to merge the smaller numbers first to increase the count. We also use the prefix sum to find the numbers’ sum and check for the condition with the next number. We also keep a variable (say, ‘IDX’) to store the index till which we cannot find any combination. The last number in the array will always be a combination because it is larger than all the array elements, so the sum can be placed at its position.
Here is the algorithm :
- Sort the array ‘ARR’.
- Create a variable (say, ‘TEMP’) that will store the prefix sum and initialize it with ‘ARR[0]’.
- Create a variable (say, ‘IDX’) that will store the index till which no combination can be formed and initialize it with 0.
- Run a loop from 0 to ‘N’ - 1 (say, iterator ‘i’) to iterate through the array.
- Check if 2 * ‘ARR[i]’ is smaller than ‘ARR[i + 1]’.
- Update ‘IDX’ by ‘i’ + 1.
- Increase ‘TEMP’ by ‘ARR[i + 1]’ to maintain prefix sum.
- Update ‘ARR[i + 1]’ by ‘TEMP’.
- Check if 2 * ‘ARR[i]’ is smaller than ‘ARR[i + 1]’.
- Finally, return ‘N’ - ‘IDX’.