Equilibrium

Hard
0/120
Average time to solve is 30m
profile
Contributed by
0 upvote
Asked in company
Uber

Problem statement

There are ‘N’ water balls arranged in a line. Some of them are hot water balls, and some are cold, i.e., temperatures of balls may be negative, zero or positive. You have an empty bag with you, and you will be collecting some balls in this bag, starting from left to right.

For each ball, you decide whether to collect this ball or not. Once you collect a ball, you can’t drop it, and you can’t go left from any position.

Total temperature of the bag at any moment is the sum of temperatures of water balls collected in it till that moment. Your task is to find the maximum number of balls you can collect, such that the total temperature of your bag must not go negative at any instance.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains ‘T’, denoting the number of tests.
For each Test :
    The first line contains an integer ‘N’, denoting the number of water balls.
    The second line contains an array ‘A’ of length ‘N’, denoting the temperatures of water balls.
Output Format: 
For each test, print an integer, denoting the maximum number of balls you can collect, such that the total temperature of the bag is non-negative at each instance.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints - 
1 <= T <= 5
1 <= N <= 10^5
-10^9 <= A[i] <= 10^9  i ∈  (1,N)


Time Limit: 1 sec
Sample Input 1 :
2
6
4 -4 1 -3 1 -3
3
2 -3 -1
Sample Output 1 :
5
2
Explanation for Sample Input 1 :
For case 1:
The optimal selection is to collect balls [4, 1, -3, 1, -3], where you will be able to collect five balls. For any other selection, you can’t collect more than five balls. Hence answer is 5.

For Case 2:
Optimal selection is balls [2, -1]. Hence answer is 2.
Sample Input 2 :
2
3
-1 -2 1
4
0 3 2 1
Sample Output 2:
1
4
Hint

Can you check for all possible selections of water balls?

Approaches (3)
Brute Force

Approach:  We need to find the longest subsequence such that its prefix sum at each position is non-negative. Using recursion, generate all subsequences of the given array. For each subsequence, check whether its prefix sum is non-negative at each place. If the prefix sum goes negative, ignore such a sequence; otherwise, consider its length to maximize the answer.


 

Algorithm:

  • Implement a recursive function -
    • That takes some parameters as follows -
      • Current index of the array is to be explored in subsequences.
      • Prefix sum of already existing subsequence in which current index will be used.
      • Input array and its size.
    • Returns length of possible subsequence, starting from ‘index’ (passed in argument) to end of the array.
  • Function implementation goes as follows -
    • If the prefix sum of subsequence is already negative, can't process the remaining sequence, return -1.
    • If we have reached the end of the array, then the length of the remaining sequence is 0; hence return 0.
    • Call two recursive calls to the next index as follows:
      • With adding current value to existing prefix sum. Here current value is considered; hence the answer for this call will be 1+ [next recursive call].
      • Another is without taking the current value. Here the answer will be the same from [next recursive call].
      • Return maximum answer among both cases.
  • Call the above recursion from the main solution function, for index = 0 and prefix_sum = 0. This call returns our desired answer.
Time Complexity

O(2 ^ N), where ‘N’ is the number of elements/water balls.

At each index, two recursive calls are taking place. Hence overall time complexity becomes O(2^N).

Space Complexity

O(2 ^ N), where ‘N’ is the number of elements/water balls.

Apart from recursion, we are using only constant space. The space is used by stack in recursion calls only. Hence overall space complexity is O(2^N).

Code Solution
(100% EXP penalty)
Equilibrium
Full screen
Console