Problem
Given a sorted array, find the smallest positive integer that is not the sum of a subset of the array.
Examples
Example 1
|
|
Example 2
|
|
Solution
Method 1 - Using Cumulative sum
The problem can be approached iteratively by considering the cumulative sum constructively:
- Start with the assumption that
1
is the smallest positive integer not representable using subsets of the array. - Traverse the array and see if the current number in the array extends the range of representable sums. If it does, update the range.
- If a gap is found between the current smallest non-representable integer and the next number in the array, that gap is the answer.
For example:
- If the smallest positive integer not representable is
x
and the current array element isy
, check ify ≤ x
. If true, updatex
tox + y
since subsets includingy
can also represent more integers. - If
y > x
,x
remains the answer asy
cannot build up the smallest integerx
.
Approach
The solution involves:
- Initialising a variable
smallestMissing
to1
(to represent the smallest positive integer not yet representable). - Iterating through the array and updating
smallestMissing
:- If the current array element is less than or equal to
smallestMissing
, then updatesmallestMissing
to include all possible sums with the current element. - If the current element is greater than
smallestMissing
, then break out of the loop assmallestMissing
cannot be reached by any subset.
- If the current array element is less than or equal to
- Return
smallestMissing
.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
. Explanation: We iterate through the array of sizen
, processing each element once. - 🧺 Space complexity:
O(1)
. Explanation: We use constant extra space for computations, as only one variable (smallestMissing
) is required.