Untitled

 avatar
unknown
plain_text
a year ago
1.8 kB
6
Indexable
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {-3, 2, 2};
        int d = 8;

        int[] uniqueArr = Arrays.stream(arr).distinct().toArray();

        if (d == uniqueArr.length) {
            System.out.println(0);
        } else {
           
            int[] searchSpace = findSearchSpace(uniqueArr, d);
            int left = binarySearch(uniqueArr, searchSpace[0] - d, searchSpace[1], d, true);
            int right = binarySearch(uniqueArr, searchSpace[0], searchSpace[1] + d, d, false);

            System.out.println(Math.abs(left - right));
        }
    }

    private static int[] findSearchSpace(int[] arr, int d) {
        int minVal = Arrays.stream(arr).min().getAsInt();
        int maxVal = Arrays.stream(arr).max().getAsInt();

        int left = minVal; 
        int right = maxVal; 

        return new int[]{left, right};
    }

    private static boolean binSearchHelper(int[] arr, int mid, int d) {
        int ans = 0;

        for (int value : arr) {
            ans += (Math.abs(value - mid)) * 2;
            if (ans > d) {
                return false;
            }
        }

        return ans <= d;
    }

    private static int binarySearch(int[] arr, int l, int r, int d, boolean spaceFlag) {
        boolean foundPoint = false;

        while (l <= r) {
            int m = (l + r) / 2;

            if (binSearchHelper(arr, m, d)) {
                foundPoint = true;
                if (spaceFlag) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            } else {
                if (spaceFlag) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
        }

        return foundPoint ? l : 0;
    }
}
Editor is loading...
Leave a Comment