# LC1552 - Magnetic Force Between Two Balls
## 线性关系 二分查找猜答案

class Solution {
    /*
    x: the required force == the distance
    f(x): if the distance is x, it can put f(x) balls
    */
    public int maxDistance(int[] position, int m) {
        // sanity check
        // ...
        Arrays.sort(position);
        
        int length = position.length;
        int minD = 1;
        int maxD = position[length - 1] - position[0];
        
        while (minD + 1 < maxD) {
            int midD = minD + (maxD - minD) / 2;
            if (canDistributeBallsBy(midD, m, position)) {
                minD = midD;
            } else {
                maxD = midD;
            }
        }
        
        // maximum
        if (canDistributeBallsBy(maxD, m, position)) {
            return maxD;
        }
        if (canDistributeBallsBy(minD, m, position)) {
            return minD;
        }
        return -1;
    }
    
    // inverse function
    private boolean canDistributeBallsBy(int targetD, int targetNumBalls, int[] position) {
        int length = position.length;
        int prevPos = position[0];
        int numBalls = 1;
        
        for (int i = 1; i < length; i++) {
            if (position[i] - prevPos >= targetD) {
                prevPos = position[i];
                numBalls++;
                
                if (numBalls >= targetNumBalls) {
                    return true;
                }
            }
        }
        
        return false;
    }
}