Smallest positive integer that cannot be represented as the sum of a subset of a sorted array

Problem

Given a sorted array, find the smallest positive integer that is not the sum of a subset of the array.

Examples

Example 1

Input: [1, 2, 3, 10]
Output: 7
Explanation: All numbers from 1 to 6 can be represented using subsets of the array. For example:
1 = [1], 2 = [2], 3 = [3], 4 = [1, 3], 5 = [2, 3], 6 = [1, 2, 3].
7 cannot be formed using subsets of the array.

Example 2

Input: [1, 3, 6, 10, 11, 15]
Output: 2
Explanation: The smallest positive integer that cannot be represented is 2 since 1 can be made using [1], but no subset adds up to 2.

Solution

Method 1 - Using Cumulative sum

The problem can be approached iteratively by considering the cumulative sum constructively:

1. Start with the assumption that 1 is the smallest positive integer not representable using subsets of the array.
2. Traverse the array and see if the current number in the array extends the range of representable sums. If it does, update the range.
3. 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 is y, check if y ≤ x. If true, update x to x + y since subsets including y can also represent more integers.
• If y > x, x remains the answer as y cannot build up the smallest integer x.

Approach

The solution involves:

1. Initialising a variable smallestMissing to 1 (to represent the smallest positive integer not yet representable).
2. Iterating through the array and updating smallestMissing:
   • If the current array element is less than or equal to smallestMissing, then update smallestMissing to include all possible sums with the current element.
   • If the current element is greater than smallestMissing, then break out of the loop as smallestMissing cannot be reached by any subset.
3. Return smallestMissing.

Code

Java

public class Solution {

    public int findSmallestMissingInteger(int[] arr) {
        int smallestMissing = 1; // Initialise smallest positive integer not representable
        for (int num : arr) {
            if (num <= smallestMissing) {
                smallestMissing += num; // Extend the range of representable sums
            } else {
                break; // 'num' creates a gap at smallestMissing
            }
        }
        return smallestMissing;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(
            solution.findSmallestMissingInteger(new int[] { 1, 2, 3, 10 })
        ); // Output: 7
        System.out.println(
            solution.findSmallestMissingInteger(
                new int[] { 1, 3, 6, 10, 11, 15 }
            )
        ); // Output: 2
        System.out.println(
            solution.findSmallestMissingInteger(new int[] { 1, 1, 1, 4 })
        ); // Output: 8
    }
}

Python

class Solution:
    def findSmallestMissingInteger(self, arr):
        smallestMissing = 1  # Initialise smallest positive integer not representable
        for num in arr:
            if num <= smallestMissing:
                smallestMissing += num  # Extend the range of representable sums
            else:
                break  # 'num' creates a gap at smallestMissing
        return smallestMissing

# Example Usage:
solution = Solution()
print(solution.findSmallestMissingInteger([1, 2, 3, 10]))  # Output: 7
print(solution.findSmallestMissingInteger([1, 3, 6, 10, 11, 15]))  # Output: 2
print(solution.findSmallestMissingInteger([1, 1, 1, 4]))  # Output: 8

Complexity

• ⏰ Time complexity: O(n). Explanation: We iterate through the array of size n, processing each element once.
• 🧺 Space complexity: O(1). Explanation: We use constant extra space for computations, as only one variable ( smallestMissing ) is required.