All Tracks Algorithms Searching Binary Search Problem

Monk and Special Integer
Tag(s):

Algorithms, Binary Search, Easy-Medium

Problem
Editorial
Analytics

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.

Constraints:
$$1 \le N \le 10^5$$
$$1\le X \le 10^{18}$$
$$1 \le A[i] \le min(X, 10^9)$$

SAMPLE INPUT
4 8
1 2 3 4

SAMPLE OUTPUT
2
Explanation

Sum of all subarrays of size $$1$$: $$1, 2, 3, 4$$
Sum of all subarrays of size $$2$$: $$3, 5, 7$$
Sum of all subarrays of size $$3$$: $$6, 9$$
Sum of all subarrays of size $$4$$: $$10$$
So clearly, maximum subarray size, such that all subarrays of that size have sum of elements less than $$8$$ is $$2$$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Searching)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications