How to find the smallest positive integer that is not the sum of integers in any sub-multiset of a given sorted array
How is the smallest positive integer related to the sum of integers of any sub-multiset?
If you think about it,
The smallest positive integer is always = (the maximum number that the sum of integers in any sub-multiset can represent) + 1.
… because this is the very next integer that cannot be represented by the sum of any sub-multiset. In other words, if the sum of integers in any sub-multiset can represent numbers from 1 to k - 1, then the smallest positive integer = k.
How do we express the above in a Systematic way?
Since we are given a sorted array, we start by scanning through each integer in the array. We can let the array be a.
In addition, we can keep track of the current smallest integer that cannot be represented by the sum of integers in any the sub-multiset we have scanned so far. Let the maximum number that the sum of integers in any sub-multiset of the numbers we have scanned so far be k - 1. Let the current smallest integer that satisfies the conditions be k.
At any point, when scanning integer a[i], there are 2 cases.
The first is k < a[i]. This means that a[i] + sum of integers in any sub-multiset (which could represent up to k - 1) can never be k. Hence k is the answer. We can stop the scan and return the answer.
The second is k ≥ a[i]. This means that a[i] + sum of integers in any sub-multiset can now represent up to k - 1 + a[i]. Hence k is not the answer, and the current smallest integer has to be updated to (k - 1 + a[i]) + 1, which = k + a[i]. Then we have to continue scanning through the integers in the array until we observe case 1.
Efficiency of this Method
This method is very efficient as it only involves a linear scan through the entire array. Hence, for an array of n integers, the time complexity is O(n).
Hope that this has been helpful. Try working out an example yourself, let’s say an array [1, 1, 3, 4, 11]. The smallest integer the satisfies the conditions is 10. Happy trying!
