find the smallest integer which cannot be represented as the sum of any of the subset of the given array.

We have been given a sorted array in increasing order of only positive values, now it is required to find the smallest positive integer value which cannot be represented as the sum of elements of any subset of given set.

The requirement is to solve the problem in time complexity is O(n).

public class SmallestIntegerThatIsNotSumInArray {

	private static int FindSmallestInteger(int[] arr) {
		int res = 1;
		for(int i=0;i< arr.length && arr[i]<= res;i++) {
			res += arr[i];
		}
		return res;
	}
	
	public static void main(String[] args) {
		
		int arr2[] = {1, 1, 3, 4};
		
		long startTime = System.nanoTime();
		
		System.out.println(FindSmallestInteger(arr2));
		
		long endTime = System.nanoTime();
		long totalTime = endTime - startTime;
		System.out.println("Total Time (nanoseconds) : " + (totalTime));
	}
}

output :

10
Total Time (nanoseconds) : 288471