# Find the smallest positive integer value that cannot be represented as sum of any subset of a given array

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

A **Simple Solution** is to start from value 1 and check all values one by one if they can sum to values in the given array. This solution is very inefficient as it reduces to subset sum problem which is a well known NP Complete Problem.

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’, there are following two possibilities when we consider element at index i:* 1) 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 by arr[i] (why? 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’)*

**2) The value of ‘res’ is incremented after considering arr[i]**Following is the implementation of above idea.

## C++

`// C++ program to find the smallest positive value that cannot be` `// represented as sum of subsets of a given sorted array` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Returns the smallest number that cannot be represented as sum` `// of subset of elements from set represented by sorted array arr[0..n-1]` `int` `findSmallest(` `int` `arr[], ` `int` `n)` `{` ` ` `int` `res = 1; ` `// Initialize result` ` ` `// Traverse the array and increment 'res' if arr[i] is` ` ` `// smaller than or equal to 'res'.` ` ` `for` `(` `int` `i = 0; i < n && arr[i] <= res; i++)` ` ` `res = res + arr[i];` ` ` `return` `res;` `}` `// Driver program to test above function` `int` `main()` `{` ` ` `int` `arr1[] = {1, 3, 4, 5};` ` ` `int` `n1 = ` `sizeof` `(arr1)/` `sizeof` `(arr1[0]);` ` ` `cout << findSmallest(arr1, n1) << endl;` ` ` `int` `arr2[] = {1, 2, 6, 10, 11, 15};` ` ` `int` `n2 = ` `sizeof` `(arr2)/` `sizeof` `(arr2[0]);` ` ` `cout << findSmallest(arr2, n2) << endl;` ` ` `int` `arr3[] = {1, 1, 1, 1};` ` ` `int` `n3 = ` `sizeof` `(arr3)/` `sizeof` `(arr3[0]);` ` ` `cout << findSmallest(arr3, n3) << endl;` ` ` `int` `arr4[] = {1, 1, 3, 4};` ` ` `int` `n4 = ` `sizeof` `(arr4)/` `sizeof` `(arr4[0]);` ` ` `cout << findSmallest(arr4, n4) << endl;` ` ` `return` `0;` `}` |

## Java

`// Java program to find the smallest positive value that cannot be` `// represented as sum of subsets of a given sorted array` `class` `FindSmallestInteger ` `{` ` ` `// Returns the smallest number that cannot be represented as sum` ` ` `// of subset of elements from set represented by sorted array arr[0..n-1]` ` ` `int` `findSmallest(` `int` `arr[], ` `int` `n) ` ` ` `{` ` ` `int` `res = ` `1` `; ` `// Initialize result` ` ` `// Traverse the array and increment 'res' if arr[i] is` ` ` `// smaller than or equal to 'res'.` ` ` `for` `(` `int` `i = ` `0` `; i < n && arr[i] <= res; i++)` ` ` `res = res + arr[i];` ` ` `return` `res;` ` ` `}` ` ` `// Driver program to test above functions` ` ` `public` `static` `void` `main(String[] args) ` ` ` `{` ` ` `FindSmallestInteger small = ` `new` `FindSmallestInteger();` ` ` `int` `arr1[] = {` `1` `, ` `3` `, ` `4` `, ` `5` `};` ` ` `int` `n1 = arr1.length;` ` ` `System.out.println(small.findSmallest(arr1, n1));` ` ` `int` `arr2[] = {` `1` `, ` `2` `, ` `6` `, ` `10` `, ` `11` `, ` `15` `};` ` ` `int` `n2 = arr2.length;` ` ` `System.out.println(small.findSmallest(arr2, n2));` ` ` `int` `arr3[] = {` `1` `, ` `1` `, ` `1` `, ` `1` `};` ` ` `int` `n3 = arr3.length;` ` ` `System.out.println(small.findSmallest(arr3, n3));` ` ` `int` `arr4[] = {` `1` `, ` `1` `, ` `3` `, ` `4` `};` ` ` `int` `n4 = arr4.length;` ` ` `System.out.println(small.findSmallest(arr4, n4));` ` ` `}` `}` `// This code has been contributed by Mayank Jaiswal(mayank_24)` |

## Python3

`# Python3 program to find the smallest` `# positive value that cannot be` `# represented as sum of subsets ` `# of a given sorted array` `# Returns the smallest number ` `# that cannot be represented as sum` `# of subset of elements from set` `# represented by sorted array arr[0..n-1]` `def` `findSmallest(arr, n):` ` ` `res ` `=` `1` `#Initialize result` ` ` `# Traverse the array and increment` ` ` `# 'res' if arr[i] is smaller than` ` ` `# or equal to 'res'.` ` ` `for` `i ` `in` `range` `(` `0` `, n ):` ` ` `if` `arr[i] <` `=` `res:` ` ` `res ` `=` `res ` `+` `arr[i]` ` ` `else` `:` ` ` `break` ` ` `return` `res` `# Driver program to test above function` `arr1 ` `=` `[` `1` `, ` `3` `, ` `4` `, ` `5` `]` `n1 ` `=` `len` `(arr1)` `print` `(findSmallest(arr1, n1))` `arr2` `=` `[` `1` `, ` `2` `, ` `6` `, ` `10` `, ` `11` `, ` `15` `]` `n2 ` `=` `len` `(arr2)` `print` `(findSmallest(arr2, n2))` `arr3` `=` `[` `1` `, ` `1` `, ` `1` `, ` `1` `]` `n3 ` `=` `len` `(arr3)` `print` `(findSmallest(arr3, n3))` `arr4 ` `=` `[` `1` `, ` `1` `, ` `3` `, ` `4` `]` `n4 ` `=` `len` `(arr4)` `print` `(findSmallest(arr4, n4))` `# This code is.contributed by Smitha Dinesh Semwal` |

## C#

`// C# program to find the smallest` `// positive value that cannot be` `// represented as sum of subsets ` `// of a given sorted array` `using` `System;` `class` `GFG {` ` ` ` ` `// Returns the smallest number that` ` ` `// cannot be represented as sum` ` ` `// of subset of elements from set ` ` ` `// represented by sorted array` ` ` `// arr[0..n-1]` ` ` `static` `int` `findSmallest(` `int` `[]arr, ` `int` `n) ` ` ` `{` ` ` `// Initialize result` ` ` `int` `res = 1;` ` ` `// Traverse the array and ` ` ` `// increment 'res' if arr[i] is` ` ` `// smaller than or equal to 'res'.` ` ` `for` `(` `int` `i = 0; i < n && ` ` ` `arr[i] <= res; i++)` ` ` `res = res + arr[i];` ` ` `return` `res;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `Main() ` ` ` `{` ` ` `int` `[]arr1 = {1, 3, 4, 5};` ` ` `int` `n1 = arr1.Length;` ` ` `Console.WriteLine(findSmallest(arr1, n1));` ` ` `int` `[]arr2 = {1, 2, 6, 10, 11, 15};` ` ` `int` `n2 = arr2.Length;` ` ` `Console.WriteLine(findSmallest(arr2, n2));` ` ` `int` `[]arr3 = {1, 1, 1, 1};` ` ` `int` `n3 = arr3.Length;` ` ` `Console.WriteLine(findSmallest(arr3, n3));` ` ` `int` `[]arr4 = {1, 1, 3, 4};` ` ` `int` `n4 = arr4.Length;` ` ` `Console.WriteLine(findSmallest(arr4, n4));` ` ` `}` `}` `// This code is contributed by Sam007` |

## PHP

`<?php` `// PHP program to find the smallest` `// positive value that cannot be` `// represented as sum of subsets` `// of a given sorted array` `// Returns the smallest number that` `// cannot be represented as sum of ` `// subset of elements from set` `// represented by sorted array ` `// arr[0..n-1]` `function` `findSmallest(` `$arr` `, ` `$n` `)` `{` ` ` ` ` `// Initialize result` ` ` `$res` `= 1; ` ` ` ` ` `// Traverse the array and ` ` ` `// increment 'res' if arr[i] is` ` ` `// smaller than or equal to 'res'.` ` ` `for` `(` `$i` `= 0; ` `$i` `< ` `$n` `and` `$arr` `[` `$i` `] <= ` `$res` `; ` `$i` `++)` ` ` `$res` `= ` `$res` `+ ` `$arr` `[` `$i` `];` ` ` ` ` `return` `$res` `;` `}` `// Driver Code` `$arr1` `= ` `array` `(1, 3, 4, 5);` `$n1` `= ` `count` `(` `$arr1` `);` `echo` `findSmallest(` `$arr1` `, ` `$n1` `),` `"\n"` `;` `$arr2` `= ` `array` `(1, 2, 6, 10, 11, 15);` `$n2` `= ` `count` `(` `$arr2` `);` `echo` `findSmallest(` `$arr2` `, ` `$n2` `),` `"\n"` `;` `$arr3` `= ` `array` `(1, 1, 1, 1);` `$n3` `= ` `count` `(` `$arr3` `);` `echo` `findSmallest(` `$arr3` `, ` `$n3` `),` `"\n"` `;` `$arr4` `= ` `array` `(1, 1, 3, 4);` `$n4` `= ` `count` `(` `$arr4` `);` `echo` `findSmallest(` `$arr4` `, ` `$n4` `);` `// This code is contributed by anuj_67.` `?>` |

## Javascript

`<script>` `// javascript program to find the smallest positive value that cannot be` `// represented as sum of subsets of a given sorted array` ` ` `// Returns the smallest number that cannot be represented as sum` ` ` `// of subset of elements from set represented by sorted array arr[0..n-1]` ` ` `function` `findSmallest(arr , n)` ` ` `{` ` ` `var` `res = 1; ` `// Initialize result` ` ` `// Traverse the array and increment 'res' if arr[i] is` ` ` `// smaller than or equal to 'res'.` ` ` `for` `(i = 0; i < n && arr[i] <= res; i++)` ` ` `res = res + arr[i];` ` ` `return` `res;` ` ` `}` ` ` `// Driver program to test above functions` ` ` `var` `arr1 = [ 1, 3, 4, 5 ];` ` ` `var` `n1 = arr1.length;` ` ` `document.write(findSmallest(arr1, n1)+` `"<br/>"` `);` ` ` `var` `arr2 = [ 1, 2, 6, 10, 11, 15 ];` ` ` `var` `n2 = arr2.length;` ` ` `document.write(findSmallest(arr2, n2)+` `"<br/>"` `);` ` ` `var` `arr3 = [ 1, 1, 1, 1 ];` ` ` `var` `n3 = arr3.length;` ` ` `document.write(findSmallest(arr3, n3)+` `"<br/>"` `);` ` ` `var` `arr4 = [ 1, 1, 3, 4 ];` ` ` `var` `n4 = arr4.length;` ` ` `document.write(findSmallest(arr4, n4)+` `"<br/>"` `);` `// This code is contributed by aashish1995` `</script>` |

Output:

2 4 5 10

Time Complexity of above program is O(n).

This article is contributed by **Rahul Gupta**. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.