add 1228

fishercoder1534 · fishercoder1534 · commit 9d028fee20a4 · 2019-12-12T08:53:29.000-08:00
diff --git a/README.md b/README.md
@@ -19,6 +19,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1237|[Find Positive Integer Solution for a Given Equation](https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1237.java) | | | |Easy||
 |1243|[Array Transformation](https://leetcode.com/problems/array-transformation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1243.java) |  |  | [:tv:](https://www.youtube.com/watch?v=MQ2i4T1l-Gs)|Easy||
 |1232|[Check If It Is a Straight Line](https://leetcode.com/problems/check-if-it-is-a-straight-line/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1232.java) |  |  | |Easy||
+|1228|[Missing Number In Arithmetic Progression](https://leetcode.com/problems/missing-number-in-arithmetic-progression/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1228.java) |  |  | |Easy||
 |1217|[Play with Chips](https://leetcode.com/problems/play-with-chips/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1217.java) |  |  | |Easy||
 |1213|[Intersection of Three Sorted Arrays](https://leetcode.com/problems/intersection-of-three-sorted-arrays/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1213.java) |  |  | [:tv:](https://www.youtube.com/watch?v=zceoOrHSHNQ)|Easy||
 |1207|[Unique Number of Occurrences](https://leetcode.com/problems/unique-number-of-occurrences/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1207.java) | O(n) | O(1) | [:tv:](https://www.youtube.com/watch?v=_NYimlZY1PE)|Easy||
diff --git a/src/main/java/com/fishercoder/solutions/_1228.java b/src/main/java/com/fishercoder/solutions/_1228.java
@@ -0,0 +1,66 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * 1228. Missing Number In Arithmetic Progression
+ *
+ * In some array arr, the values were in arithmetic progression: the values arr[i+1] - arr[i] are all equal for every 0 <= i < arr.length - 1.
+ * Then, a value from arr was removed that was not the first or last value in the array.
+ * Return the removed value.
+ *
+ * Example 1:
+ * Input: arr = [5,7,11,13]
+ * Output: 9
+ * Explanation: The previous array was [5,7,9,11,13].
+ *
+ * Example 2:
+ * Input: arr = [15,13,12]
+ * Output: 14
+ * Explanation: The previous array was [15,14,13,12].
+ *
+ * Constraints:
+ * 3 <= arr.length <= 1000
+ * 0 <= arr[i] <= 10^5
+ * */
+public class _1228 {
+    public static class Solution1 {
+        /**A super verbose and inefficient but working way...*/
+        public int missingNumber(int[] arr) {
+            Arrays.sort(arr);
+            Map<Integer, List<Integer>> map = new HashMap<>();
+            for (int i = 0; i < arr.length - 1; i++) {
+                int diff = arr[i + 1] - arr[i];
+                List<Integer> list = map.getOrDefault(diff, new ArrayList<>());
+                list.add(i);
+                map.put(diff, list);
+            }
+            int smallDiff = arr[arr.length - 1];
+            int bigDiff = 0;
+            for (int key : map.keySet()) {
+                smallDiff = Math.min(smallDiff, key);
+                bigDiff = Math.max(bigDiff, key);
+            }
+            return arr[map.get(bigDiff).get(0)] + smallDiff;
+        }
+    }
+
+    public static class Solution2 {
+        /**credit: https://leetcode.com/problems/missing-number-in-arithmetic-progression/discuss/408474/JavaC%2B%2BPython-Arithmetic-Sum-and-Binary-Search*/
+        public int missingNumber(int[] arr) {
+            int min = arr[0];
+            int max = arr[0];
+            int sum = 0;
+            for (int num : arr) {
+                max = Math.max(max, num);
+                min = Math.min(min, num);
+                sum += num;
+            }
+            return (max + min) * (arr.length + 1) / 2 - sum;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1228Test.java b/src/test/java/com/fishercoder/_1228Test.java
@@ -0,0 +1,31 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1228;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1228Test {
+    private static _1228.Solution1 solution1;
+    private static _1228.Solution2 solution2;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1228.Solution1();
+        solution2 = new _1228.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(9, solution1.missingNumber(new int[]{5, 7, 11, 13}));
+        assertEquals(9, solution2.missingNumber(new int[]{5, 7, 11, 13}));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(14, solution1.missingNumber(new int[]{15, 13, 12}));
+        assertEquals(14, solution2.missingNumber(new int[]{15, 13, 12}));
+    }
+
+}
