Official algorithmic problem description and constraints.
An array A of length N containing positive integers is said to be superincreasing if each element is strictly greater than the sum of all the previous elements.
That is, for each i from 2 to N, the condition Ai>A1+A2+…+Ai−1should hold.
For example, A=[3,5,10,42] is a superincreasing array, while A=[1,2,3] is not (3=1+2, but it should be strictly greater than that).Chef had a superincreasing array A of length N with him a long time ago, but has forgotten all its elements now.
The only piece of information he recalls is that the value X occurred at index K of the array, i.e, AK=X.
Can you tell Chef if he recalls correctly?
That is, does there exist a superincreasing array A of length N such that AK=X?
Detailed video explanations, mathematical intuition, and clean C++ implementation code.
