leetcode Problem 01 first try

shekhargulati · shekhargulati · commit 8575e8ca4259 · 2016-03-02T18:08:13.000+05:30
diff --git a/java8/src/main/java/com/shekhargulati/leetcode/Problem01.java b/java8/src/main/java/com/shekhargulati/leetcode/Problem01.java
@@ -43,6 +43,29 @@ public static int[] twoSum(int[] numbers, int target) {
         return new int[0];
     }
 
+    /*
+    Assume array is sorted then you can do it O(n)
+     */
+    public static int[] twoSum_binarySearch(int[] numbers, int target) {
+        /*
+        Algorithm:
+        1. Iterate over all the numbers and find the second number by subtracting the first from target
+        2. Find the second number from the sorted array.
+        3. If second number is found then return index of first and second and second else move to the next number.
+         */
+        for (int i = 0; i < numbers.length; i++) {
+            int first = numbers[0];
+            if (first < target) {
+                int second = target - first;
+                int secondElementIndex = Arrays.binarySearch(numbers, second);
+                if (secondElementIndex >= 0) {
+                    return new int[]{i, secondElementIndex};
+                }
+            }
+        }
+        return new int[0];
+    }
+
 
     /*
     This solution in O(n^2)
diff --git a/java8/src/test/java/com/shekhargulati/leetcode/Problem01Test.java b/java8/src/test/java/com/shekhargulati/leetcode/Problem01Test.java
@@ -35,4 +35,16 @@ public void shouldWorkOnARandomArray() throws Exception {
         assertThat(pairs.length, equalTo(2));
 
     }
+
+    @Test
+    public void shouldFindTwoNumberWhoseSumIsEqualToTarget_sorted_binarySearch() throws Exception {
+        int[] pairs = Problem01.twoSum_binarySearch(new int[]{2, 7, 11, 15}, 9);
+        assertTrue(Arrays.equals(pairs, new int[]{0, 1}));
+    }
+
+    @Test
+    public void shouldReturnEmptyArrayWhenNoTwoElementsInTheArrayHaveSum_sorted_binarySearch() throws Exception {
+        int[] pairs = Problem01.twoSum_binarySearch(new int[]{2, 7, 11, 15}, 12);
+        assertTrue(Arrays.equals(pairs, new int[0]));
+    }
 }
