Question

Algorithm to find the smallest integer value that can't be represented as sum of any subset of a given array.

Answer 1

Answer:

Given a sorted array (sorted in non-decreasing order) of positive numbers, find the smallest positive integer value that cannot be represented as sum of elements of any subset of given set.

Expected time complexity is O(n).

Examples:

Input: arr[] = {1, 3, 6, 10, 11, 15};

Output: 2

Input: arr[] = {1, 1, 1, 1};

Output: 5

Input: arr[] = {1, 1, 3, 4};

Output: 10

Input: arr[] = {1, 2, 5, 10, 20, 40};

Output: 4

Input: arr[] = {1, 2, 3, 4, 5, 6};

Output: 22

...

Answer 2

Answer:

Consider all integers in interval [2i .. 2i+1 - 1]. And suppose all integers below 2i can be formed from sum of numbers from given array. Also suppose that we already know C, which is sum of all numbers below 2i. If C >= 2i+1 - 1, every number in this interval may be represented as sum of given numbers. Otherwise we could check if interval [2i .. C + 1] contains any number from given array. And if there is no such number, C + 1 is what we searched for.