Find the smallest integer that cannot be represented as sum of any subset of sorted array

Problem

Given a sorted array of positive integers, find out the smallest integer which cannot be represented as the sum of any subset of the array.

Examples

Example 1:

Input: [1, 2, 3, 8, 9, 10]
Output: 7
Explanation: All integers from 1 to 6 can be represented as a sum of subsets of the array, but 7 cannot.

Example 2:

Input: [1, 1, 3, 4]
Output: 10
Explanation: All integers from 1 to 9 can be represented as a sum of subsets of the array, but 10 cannot.

Example 3:

Input: [1, 2, 5, 11, 15]
Output: 4
Explanation: All integers from 1 to 3 can be represented as a sum of subsets of the array, but 4 cannot.

Solution

Method 1 - Incremental gap technique for smallest non-representable integer

To find the smallest integer that cannot be represented as the sum of any subset of the array:

1. Initialize a variable to track the smallest integer that cannot be represented (res = 1).
2. Iterate through the array, and for each element:
   • If the current element is less than or equal to res, increment res by the value of the current element. This means that we can represent any number up to res as the sum of subsets of the array.
   • If the current element is greater than res, then res is the smallest number that cannot be represented as the sum of any subset of the array.
3. Return the value of res.

Code

Java

public class Solution {
    public int findSmallestNonRepresentable(int[] arr) {
        int res = 1; // Initialize result

        for (int num : arr) {
            if (num <= res) {
                res += num;
            } else {
                break;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] arr1 = {1, 2, 3, 8, 9, 10};
        System.out.println(
            solution.findSmallestNonRepresentable(arr1)); // Output: 7

        int[] arr2 = {1, 1, 3, 4};
        System.out.println(
            solution.findSmallestNonRepresentable(arr2)); // Output: 10

        int[] arr3 = {1, 2, 5, 11, 15};
        System.out.println(
            solution.findSmallestNonRepresentable(arr3)); // Output: 4
    }
}

Python

def findSmallestNonRepresentable(arr):
    res = 1  # Initialize result

    for num in arr:
        if num <= res:
            res += num
        else:
            break

    return res


# Example usage:
arr1 = [1, 2, 3, 8, 9, 10]
print(findSmallestNonRepresentable(arr1))  # Output: 7

arr2 = [1, 1, 3, 4]
print(findSmallestNonRepresentable(arr2))  # Output: 10

arr3 = [1, 2, 5, 11, 15]
print(findSmallestNonRepresentable(arr3))  # Output: 4

Complexity

• ⏰ Time complexity: O(n), because we iterate through the array once.
• 🧺 Space complexity: O(1) because we use a constant amount of extra space.