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;
        }
    }
}

@@ -158,625 +158,8 @@
 p;%0A%0A
-/**%0A * 1228. Missing Number In Arithmetic Progression%0A *%0A * In some array arr, the values were in arithmetic progression: the values arr%5Bi+1%5D - arr%5Bi%5D are all equal for every 0 %3C= i %3C arr.length - 1.%0A * Then, a value from arr was removed that was not the first or last value in the array.%0A * Return the removed value.%0A *%0A * Example 1:%0A * Input: arr = %5B5,7,11,13%5D%0A * Output: 9%0A * Explanation: The previous array was %5B5,7,9,11,13%5D.%0A *%0A * Example 2:%0A * Input: arr = %5B15,13,12%5D%0A * Output: 14%0A * Explanation: The previous array was %5B15,14,13,12%5D.%0A *%0A * Constraints:%0A * 3 %3C= arr.length %3C= 1000%0A * 0 %3C= arr%5Bi%5D %3C= 10%5E5%0A * */%0A
 publ
@@ -222,16 +222,28 @@
      /**
+%0A         * 
 A super 
@@ -284,16 +284,26 @@
 g way...
+%0A         
 */%0A     
@@ -1063,16 +1063,28 @@
      /**
+%0A         * 
 credit: 
@@ -1219,16 +1219,26 @@
 y-Search
+%0A         
 */%0A     

refactor 1228