Given an array of +ve and -ve no. where +ve number represents earning and -ve represents expenditure.
You can move the -ve values at the end which is considered as one operation.
Find the minimum no of operations req. such that sum of array never reaches -ve
U can assume that sum of total array is always non negative.
N = [1,100000]
A[i] =[-100000,100000]
Exp
Arr = 10,-10,1,-2,-1,-2,4
Ans = 1 as moving -10 would be enough to make sure the sum of array at any point is non negative.
Now able find an efficient soln.
Recursion would produce tle .
Can you provide question link?
1 Like
I don’t have the question link, it was asked in the online assesment of a company.
Start iterating from the start and add the present value to a variable sum which is initialized to 0 at the beginning and also add the value to a multiset.
If at any point the sum < 0, this means some negative value needs to be removed.
And it’s always optimal to remove the minimum value.
So query the multiset for the minimum value.
Let it be x.
update sum = sum - x, ans++
1 Like
Thank you @daanish_adm for the soln. Looking at it i feel like i have put more effort on coding…
Thanks again…