package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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

@@ -1599,11 +1599,929 @@
  %7D%0A    %7D
+%0A%0A    public static class Solution3 %7B%0A        public int missingNumber(int%5B%5D arr) %7B%0A            if (arr%5B1%5D %3C arr%5B0%5D) %7B%0A                reverse(arr);%0A            %7D%0A            int diff = -1;%0A            for (int i = 0; i %3C arr.length - 1; i++) %7B%0A                if (i == 0) %7B%0A                    diff = arr%5Bi + 1%5D - arr%5Bi%5D;%0A                %7D else if (arr%5Bi + 1%5D - arr%5Bi%5D %3E diff) %7B%0A                    return arr%5Bi%5D + diff;%0A                %7D else if (arr%5Bi + 1%5D - arr%5Bi%5D %3C diff) %7B%0A                    return arr%5Bi%5D - (arr%5Bi + 1%5D - arr%5Bi%5D);%0A                %7D%0A            %7D%0A            return arr%5Barr.length - 1%5D;%0A        %7D%0A%0A        private void reverse(int%5B%5D arr) %7B%0A            int i = 0;%0A            int j = arr.length - 1;%0A            while (i %3C j) %7B%0A                int tmp = arr%5Bi%5D;%0A                arr%5Bi%5D = arr%5Bj%5D;%0A                arr%5Bj%5D = tmp;%0A                i++;%0A                j--;%0A            %7D%0A        %7D%0A    %7D
 %0A%7D%0A

add a solution for 1228