Find Smallest Integer
You are given an array 'ARR' consisting of 'N' positive numbers and sorted in non-decreasing order, and your task is to find the smallest positive integer value that cannot be represented as a sum of elements of any proper subset of the given array.

An array 'B' is a subset of another array 'A' if each element of 'B' is present in 'A'.

For example:

For the given input array [1, 1, 3], 1 can be represented as the sum of elements of the subset [1], 2 can be represented as the sum of elements of a subset [1, 1], 3 can be represented as the sum of elements of a subset [3], 4 can be represented as the sum of elements of a subset [1, 3], 5 can be represented as the sum of elements of a subset [1, 1, 3] So, the smallest positive integer value that cannot be represented as a sum of elements of any subset of a given array is 6.

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow. The first line of each test case contains an integer ‘N’ representing the size of the input array. The second line of each test case contains elements of the array separated by a single space.

Output Format:

For each test case, the only line of output prints a single integer representing the smallest positive integer value that cannot be represented as a sum of any subset of the given array. Output for each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of.

Constraints:

1

Question

Find Smallest Integer

You are given an array 'ARR' consisting of 'N' positive numbers and sorted in non-decreasing order, and your task is to find the smallest positive integer value that cannot be represented as a sum of elements of any proper subset of the given array.

An array 'B' is a subset of another array 'A' if each element of 'B' is present in 'A'.

For example:

For the given input array [1, 1, 3],
1 can be represented as the sum of elements of the subset [1],
2 can be represented as the sum of elements of a subset [1, 1],
3 can be represented as the sum of elements of a subset [3],
4 can be represented as the sum of elements of a subset [1, 3],
5 can be represented as the sum of elements of a subset [1, 1, 3]
So, the smallest positive integer value that cannot be represented as a sum of elements of any subset of a given array is 6.

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The first line of each test case contains an integer ‘N’ representing the size of the input array.

The second line of each test case contains elements of the array separated by a single space.

Output Format:

For each test case, the only line of output prints a single integer representing the smallest positive integer value that cannot be represented as a sum of any subset of the given array.

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of.

Constraints:

1 <= T <= 100
1 <= N <= 10^4
0 <= arr[i] <= 10^9

Where 'T' represents the number of test cases, 'N' represents the size of the array, and 'arr[i]' represents the elements of the array.  
Time Limit: 1 sec.

Accepted Answer

Brute force Approach

The brute force approach for this problem is explained below:

We can generate all possible 2 ^ N subsets where ‘N’ is the number of elements in the array.
Compute the sum of each subset.
Insert those sums into a HashSet and then
Run a loop i: 1 -> Integer.MAX_VALUE to check if ‘i’ is present in the hashSet. The first element that is missing from the hashSet is our answer.

We will use a recursive approach to find a subset, where we backtrack each solution after appending the subset to the resultset. The thought is that if we have N number of elements inside an array, we have exactly two choices for each of them; either we include that element in our subset or we do not include it. So, the take or not take strategy builds a pseudo-binary tree of choices returning only the leaves for each combination resulting in the powerset.

Here are the steps to generate subsets:

Check for the base case, i.e., if startIndex > endIndex, then add the current subset-sum into the HashSet.
Recursively call a subset including arr[l] i.e. subsetSums(arr, l + 1, r, arr[l] + sum).
Recursively call a subset excluding arr[l] i.e. subsetSums(arr, l + 1, r, sum).

Space Complexity: O(1)Explanation:

O(N), where ‘N’ is the size of the given array.

Since we are using a HashSet to store the sum of each subset of the given input array thus, the space complexity will be O(N).

Time Complexity: O(1)Explanation:

O(2 ^ N), where ‘N’ is the size of the given array.

Generating subsets is an NP-Complete problem, and so there is no polynomial-time solution for it. Therefore, the time complexity of this approach is O(2 ^ N).

Accepted Answer

Optimized Approach

We can solve this problem in O(n) time using a simple loop. Let the input array be ARR[0..n-1]. We initialize the result as 1 (smallest possible outcome) and traverse the given array. Let the smallest element that cannot be represented by elements at indexes from 0 to (i - 1) be ‘res’, and there are the following two possibilities when we consider element at index i:

We decide that ‘res’ is the final result: If ARR[i] is greater than ‘res’, then we found the gap, which is ‘res’ because the elements after ARR[i] are also going to be greater than ‘res’.
The value of ‘res’ is incremented after considering ARR[i]: The value of ‘res’ is incremented by ARR[i] (If elements from 0 to (i - 1) can represent 1 to ‘res - 1’, then elements from 0 to ‘i’ can represent from 1 to ‘res + ARR[i] - 1’ be adding ‘ARR[i]’ to all subsets that represent 1 to ‘res’).

Space Complexity: O(1)Explanation:

O(1), i.e., constant space complexity.

Since no extra memory is used except for some variables thus, the space complexity will be O(1).