So, first I sorted the array in ascending order.
Let’s say for example we have snakes length
3 5 9 10 12 15 18 21 and Q = 16
Now we will do a binary search to get the point where the snakes already greater or equal to 16.
Because in the above array of snakesLength we already have value 18 & 21 which is greater or equal to 10. We will not worry about those value now. we know that we already have 2 snakes that are longer than the value of K.
Now, we have to look at first six values of the array
3 5 9 10 14 15
(0 1 2 3 4 5) index
so we will do a binary search again to get the middle value of this array which is index 2. Now we calculate the sum of all elements after index 2(inclusive) so that will be 9 + 10 + 14 + 15 ==> 48. So, now we know that we need (164)-48 ==> 16 snakes to feed all these 4 snakes but we only have 2 snakes(index 0 and index 1). So, we go to the right with binary search, we get the index 3 so now 10 + 14 + 15 ==> 39, and we need (163)-39 ==> 9 snakes, but we only have 3 snakes(index 0,1,2) so we go to the right now index will be 4 and that will be 14 + 15 ==> 29 and we need (16*2)-27 ==> 4 and now we have 4 snakes (index 0,1,2,3) and that’s the maximum number we can have. so the answer will be we 2(snakes just fed) + 2(earlier snakes who were already bigger than the value of Q). Answer is 4
My code works for these values but it still gives me time limit exceed can anyone please tell me why is this happening?? Although I made a rough guess for the reason of time limit exceed that if we have 10^9 values it might getting time limit exceed because of taking the sum each time from the middle index to the right!! but I’m not sure. Or is it because long can’t hold the value of the sum because of the constraints because each value can be up to 10^9 and the size of the array can be up to 10^5. Can anyone please help me? Thanks
Sorry, I was in class. Regarding your query, firstly i calculated the index after which all snakes are of length >=k. We can directly add ans to it. Then I binary search for the index i such that, snakes needed to make length of all snakes after index i longer than k <= excess snakes (which we can be eaten up by snakes).
The main point where my code differs from yours is that i pre-computed the sum of all elements till index i and can simply re-use it. You are calculating it again and again and this is causing TLE if array is big.
“In algorithms, precomputation is the act of performing an initial computation before run time to generate a lookup table that can be used by an algorithm to avoid repeated computation each time it is executed.”
How did you precompute the sum? "The main point where my code differs from yours is that I pre-computed the sum of all elements till index i " how did you find the index i before doing binary search, is it the middle element? Please can you explain me? can you explain the logic where you precompute the sum? Thank you
Precomputing the sum upto index i is easy. We maintain an array, where arr[i] is sum of all elements from index 0,1,2…i. Now lets say i want sum of all elements from index [2,8]. Its arr[8]-arr[1]. Use this concept and precompute.
I am doing binary search for index i, as i said here Then I binary search for the index i such that, snakes needed to make length of all snakes after index i longer than k <= excess snakes (which we can be eaten up by snakes)
No, we are using the sum array in calculation. This is to avoid this part-
Now we calculate the sum of all elements after index 2(inclusive) so that will be 9 + 10 + 14 + 15 ==> 48
Computing sum of elements upto some index i can take lot of time if array is large. We are technically saving all the time taken by your loop-
for(int i = (int) lastIndex;i>=median;i--)
sum+=snakesLength[i];
Binary search is done on original array. Wherever we need things like sum etc. we refer to our second array where we stored stuff, so that we can save going through original array again and again.
