InterviewBit Academy is now Scaler!
InterviewBit Academy is now Scaler Academy!

Smallest Missing Sum!

Problem Description

Given a sorted array A (sorted in non-decreasing order) of N positive numbers.

Find the smallest positive integer value that cannot be represented as sum of elements of any subset of given set.

NOTE: If answer exceeds the range of on an Integer datatype i.e 2147483647 then return 2147483647.



Problem Constraints
  • 1 <= N <= 105
  • 1 <= A[i] <= 106


Input Format

First and only argument represents an integer array of size N denoting A.



Output Format

Return an single integer denoting smallest positive integer value that cannot be represented as sum of elements of any subset of given set.



Example Input

Input 1:

 A = [1, 1, 1, 1]

Input 2:

 A = [1, 2, 5, 10, 20, 40]



Example Output

Output 1:

 5

Output 2:

 4



Example Explanation

Explanation 1:

 Sum = 1, 2, 3, 4 is easily possible with given elements but a subset with sum of 5 is not present in the given array.

Explanation 2:

 Sum = 4 is not possible and is the smallest so this will be the answer.



NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Smallest Missing Sum! on Interview Code Editor
Sign Up
to access hints and editorial solutions for Smallest Missing Sum!

Discussion


Loading...
Click here to start solving coding interview questions