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