Reduce Array

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in companies
IntuitAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
1 3 4
2
2 1
Sample Output 1 :
2
2
Explanation For Sample Input 1 :
For test case 1: 
Combination 1: 
Pick 3 and 4 and insert their sum at the position of 4: [1, -1, 7]
Pick 1 and 7 and insert their sum at the position of 7: [-1, -1, 8]

Combination 2:
Pick 3 and 4 and insert their sum at the position of 3: [1, 7, -1]
Pick 1 and 7 and insert their sum at the position of 7: [-1, 8, -1]

So total combinations are 2.

For test case 2: 
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.
Sample Input 2 :
2
3 
4 3 5
5
2 3 4 1 5
Sample Output 2 :
3
5
Hint

Try to think of an approach by sorting the array.

Approaches (1)
Greedy Approach

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 :

 

  1. Sort the array ‘ARR’.
  2. Create a variable (say, ‘TEMP’) that will store the prefix sum and initialize it with ‘ARR[0]’.
  3. Create a variable (say, ‘IDX’) that will store the index till which no combination can be formed and initialize it with 0.
  4. 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’.
  5. Finally, return ‘N’ - ‘IDX’.
Time Complexity

O(N*log(N)), where ‘N’ is the size of the array.

 

We sort the ‘ARR’ array, which takes N*log(N) time. We also iterate ‘ARR’ once. Therefore, the overall time complexity will be O(N*log(N)).

Space Complexity

O(N), where ‘N’ is the size of the array.

 

The sort uses an extra space of ‘N’. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Reduce Array
Full screen
Console