Monk and his best friend Micro were taking a stroll, when they found an array A having N integers lying on the road. The array was injured badly, so they took it with them and treated it.

When the array came back to senses, it told them, that some crazy guy came and started beating it. The array started crying and while Monk and Micro were comforting it, the last element of the array informed that the special integer is missing from its pocket. After hearing that, the array started crying even louder because it is supposed to appear in the next Code Monk Challenge with that Special Integer.

Special integer, K, of an array, is an integer such that none of its subarray of size K has sum of elements greater than X. To calm the array down, Monk decided to gift it the maximum possible value of special integer K. Now since Monk is busy with Code Monk he asked Micro to find the maximum value of special integer but right now, all Micro can think of is a Potato, so Micro asked for your help.

Input Format: First line consists of two space separated integers denoting N and X. Second line consists of N space separated integers denoting the array A.

Output Format: Print the maximum possible value of special integer.

sample input:

4 8

1 2 3 4

sample output


Above question is on hackerearth: https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/monk-and-special-integer-code-monk/description/

I am not able to get the approach, even editorial is mentioned, and this is to be solved by binary search. What I understood was it was solved using sum of preceding values and comparing but still not very clear, please help

  • $\begingroup$ There is a simple $O(n\log n)$ algorithm that uses binary search on $K$. For a given value of $K$, you can find out the maximal sum of a subarray of size $K$ in $O(n)$. Using this, you can perform $\log n$ steps of binary search to find $K$. $\endgroup$ Jun 18, 2018 at 13:03
  • $\begingroup$ Perhaps you could remove the silly problem description and replace it with a more succinct one. $\endgroup$ Jun 18, 2018 at 13:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.