Not a Subset Sum

Given a sorted array arr[] of positive integers, find the smallest positive integer such that it cannot be represented as the sum of elements of any subset of the given array set.

Examples:

Input: arr[] = [1, 2, 3]
Output: 7
Explanation: 7 is the smallest positive number for which no subset is there with sum 7.

Input: arr[] = [3, 6, 9, 10, 20, 28]
Output: 1
Explanation: 1 is the smallest positive number for which no subset is there with sum 1.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints
1 <= arr.size()<= 10⁶
1 <= arr[i] <= 10⁸

Approach 01:

class Solution {
public:
    long long findSmallest(std::vector<int>& numbers) {
        int currentSum = 0;
        int size = numbers.size();
        
        currentSum += numbers[0];
        
        if (numbers[0] != 1) {
            return 1;
        }

        for (int i = 1; i < size; i++) {
            if (currentSum + 1 >= numbers[i]) {
                currentSum += numbers[i];
            } else {
                return currentSum + 1;
            }
        }

        return currentSum + 1;
    }
};

class Solution:
    def findSmallest(self, numbers) -> int:
        currentSum = 0
        size = len(numbers)

        currentSum += numbers[0]

        if numbers[0] != 1:
            return 1

        for i in range(1, size):
            if currentSum + 1 >= numbers[i]:
                currentSum += numbers[i]
            else:
                return currentSum + 1

        return currentSum + 1

Time Complexity

• Initialization and Base Case:

  The algorithm first checks if the smallest element of the sorted array, numbers[0], is not equal to 1. This is a constant-time operation, \(O(1)\).

• Iterating through the array:

  The main part of the algorithm involves a single for-loop that iterates through the numbers vector once, from index 1 to size - 1. This loop executes \(O(n)\) times, where \(n\) is the size of the numbers vector.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the size of the numbers vector, since the algorithm only makes a single pass through the vector.

Space Complexity

• Auxiliary Space:

  The function uses a few integer variables (currentSum and size), which require constant space, \(O(1)\). No additional data structures are used that scale with the input size.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as the algorithm only uses a fixed amount of extra space regardless of the input size.