Maximizing Minimum Distance Between Elements

Given an array of unique positions and a number of items to place, the goal is to position the items such that the minimum absolute difference between any two items' positions is maximized.

Example 1:

Input: positions = [1,2,3,4,7], items = 3
Output: 3
Explanation: Placing items at positions 1, 4, and 7 yields distances of 3, 3, and 6. The minimum distance is 3, which is the maximum possible minimum distance.

Example 2:

Input: positions = [5,4,3,2,1,1000000000], items = 2
Output: 999999999

Algorithm: Binary Search

The optimal minimum distance lies between 1 and the maximum possible distance, which is the total span divided by the number of gaps. By sorting the positions, we can use binary search to guess a minimum distance and verify its feasibility through a linear scan. If a guess is valid, we try for a larger distance; otherwise, we reduce our search space. The +1 and -1 adjustments during the search boundaries are crucial to avoid infinite loops.

function getMaxMinForce(baskets, totalBalls) {
    baskets.sort((a, b) => a - b);
    const n = baskets.length;
    let high = Math.floor((baskets[n - 1] - baskets[0]) / (totalBalls - 1));
    let low = 1;
    
    const canPlaceBalls = (minDist) => {
        let placedBalls = 1;
        let lastPos = baskets[0];
        for (let i = 1; i < n; i++) {
            if (baskets[i] - lastPos >= minDist) {
                placedBalls++;
                lastPos = baskets[i];
                if (placedBalls >= totalBalls) return true;
            }
        }
        return false;
    };
    
    let maxMinForce = 0;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (canPlaceBalls(mid)) {
            maxMinForce = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return maxMinForce;
}

Minimum Days to Consume N Items

Given n items, each day you can choose one of the following actions:

• Consume 1 item.
• If the remaining count is divisible by 2, consume half of the items.
• If the remaining count is divisible by 3, consume two-thirds of the items.

Return the minimum number of days to consume all n items.

Example 1:

Input: n = 10
Output: 4
Explanation: Day 1: eat 1, leaving 9. Day 2: eat 6 (2/3 of 9), leaving 3. Day 3: eat 2, leaving 1. Day 4: eat 1, leaving 0.

Example 2:

Input: n = 6
Output: 3

Algorithm: Memoized Depth-First Search

A standard dynamic programming array fails due to the constraint n <= 2 * 10^9, which causes memory limits and timeouts. The state space is pruned by recognizing that consuming items one by one is only optimal to reach a state where division is possible. For any count k, we compare the cost of reaching k / 2 (requiring k % 2 + 1 days) against reaching k / 3 (requiring k % 3 + 1 days). A hash map stores the computed states, leading to a logarithmic number of unique states.

function calculateMinDays(remaining) {
    const memo = new Map();
    
    const findDays = (count) => {
        if (count <= 1) return count;
        if (memo.has(count)) return memo.get(count);
        
        const eatToMultipleOf2 = (count % 2) + 1 + findDays(Math.floor(count / 2));
        const eatToMultipleOf3 = (count % 3) + 1 + findDays(Math.floor(count / 3));
        
        const result = Math.min(eatToMultipleOf2, eatToMultipleOf3);
        memo.set(count, result);
        return result;
    };
    
    return findDays(remaining);
}