Untitled
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