smallest integer not subset sum

Tushar Roy · Tushar Roy · commit 4f962b8691d5 · 2015-12-31T14:53:10.000-06:00
diff --git a/python/array/smallestintegernotrepresentedbysubsetsum.py b/python/array/smallestintegernotrepresentedbysubsetsum.py
@@ -0,0 +1,14 @@
+# http://www.geeksforgeeks.org/find-smallest-value-represented-sum-subset-given-array/
+
+def find_smallest_integer(input):
+    result = 1
+    for i in range(len(input)):
+        if input[i] <= result:
+            result += input[i]
+        else:
+            break
+    return result
+
+if __name__ == '__main__':
+    input = [1, 2, 3, 8]
+    print(find_smallest_integer(input))
diff --git a/src/com/interview/array/SmallestIntegerNotRepresentedBySubsetSum.java b/src/com/interview/array/SmallestIntegerNotRepresentedBySubsetSum.java
@@ -0,0 +1,33 @@
+package com.interview.array;
+
+/**
+ * Date 12/31/2015
+ * @author Tushar Roy
+ *
+ * Given array in non decreasing order find smallest integer which cannot be represented by
+ * subset sum of these integers.
+ *
+ * Time complexity is O(n)
+ *
+ * http://www.geeksforgeeks.org/find-smallest-value-represented-sum-subset-given-array/
+ */
+public class SmallestIntegerNotRepresentedBySubsetSum {
+
+    public int findSmallestInteger(int input[]) {
+        int result = 1;
+        for (int i = 0; i < input.length; i++) {
+            if (input[i] <= result) {
+                result += input[i];
+            } else {
+                break;
+            }
+        }
+        return result;
+    }
+
+    public static void main(String args[]) {
+        int input[] = {1, 2, 3, 8};
+        SmallestIntegerNotRepresentedBySubsetSum ss = new SmallestIntegerNotRepresentedBySubsetSum();
+        System.out.print(ss.findSmallestInteger(input));
+    }
+}
