Minimum Moves to Pick K Ones

This approach significantly optimizes the previous one by making a critical observation about the nature of the optimal solution. The cost of creating a new 1 and bringing it to the collection point is 2 moves. This sets a budget for how far an original 1 can be from the collection point. If an original 1 is more than 2 moves away from the median of the chosen group, it's cheaper to use a 'change' operation instead.

This insight proves that all original 1s in an optimal group must be very close to each other. Specifically, the distance from any chosen 1 to the group's median must be at most 2. This in turn means the total span of the indices of the chosen 1s (max_index - min_index) must be at most 4. Consequently, we only need to check contiguous windows of 1s of size up to 5, drastically reducing the search space.

1. The core insight is that in an optimal solution, any chosen original 1 at index p must be close to the median M of all chosen original 1s. Specifically, the distance |p - M| cannot be greater than 2.
2. If |p - M| > 2, it would be cheaper to discard this 1 and use a 'change' operation instead, which costs 2 moves. This would reduce the total cost, contradicting optimality.
3. This observation implies that for any chosen group of original 1s, their indices p_1, p_2, ..., p_w must satisfy max(p_i) - min(p_i) <= 4.
4. Therefore, we only need to consider contiguous windows of 1s from one_indices where the window size is at most 5.
5. The algorithm then becomes linear: iterate through each index i in one_indices as a potential start of a window.
6. For each i, consider small windows starting at i (of size up to 5). A second pointer j can find the end of such small windows efficiently.
7. For each such small window [i, j], calculate the number of original ones w = j - i + 1.
8. If k-w is a valid number of changes (0 <= k-w <= maxChanges), calculate the total cost: gather_cost(i, w) + 2 * (k-w).
9. Update the minimum cost found. Also, handle the base case of using only changes (2*k if k <= maxChanges).

The logic builds upon the previous approach but constrains the search space. We still find all one_indices and compute their prefix sums.

The key argument is as follows: Let the chosen set of w original ones be S, and their median index be M. The total cost is sum_{p in S} |p - M| + 2 * (k - w). Suppose there exists a p_j in S such that |p_j - M| > 2. We could form a new solution by removing p_j from S and using one more 'change' operation. The new cost would be sum_{p in S, p != p_j} |p - M'| + 2 * (k - w + 1), where M' is the new median. The sum of distances to the new median M' can only be less than or equal to the sum of distances to the old median M. So, the change in cost is at most 2 - |p_j - M|, which is negative if |p_j - M| > 2. This means the new solution is cheaper, a contradiction. Thus, in any optimal solution, all chosen original ones p must satisfy |p - M| <= 2.

This implies that the difference between the maximum and minimum index in the chosen group is at most 4. Since the indices are integers, such a group can have at most 5 ones.

This transforms the O(m^2) algorithm into an O(m) one. We iterate through i from 0 to m-1. For each i, we only need to check windows P[i...j] where j is at most i+4. This is a constant number of checks per i.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public long minimumMoves(int[] nums, int k, int maxChanges) {
        List<Integer> oneIndices = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                oneIndices.add(i);
            }
        }

        int m = oneIndices.size();
        if (m + maxChanges < k) {
            // Should not happen based on constraints, but good practice
            return -1; 
        }
        if (k == 0) {
            return 0;
        }

        long minMoves = Long.MAX_VALUE;

        // Case 1: Use only changes
        if (k <= maxChanges) {
            minMoves = (long)k * 2;
        }

        // Case 2: Use some original ones
        // We only need to check small groups of original ones because if any original one
        // is > 2 distance from the median, it's cheaper to use a change (cost 2).
        // This implies the span of indices is at most 4, so window size is at most 5.
        // Let's check a slightly larger bound for safety, e.g., up to 3 adjacent ones.
        // The proof shows we only need to check groups of 1, 2, or 3 ones around an index.
        for (int i = 0; i < m; i++) {
            // Option A: 1 original at P[i], k-1 changes
            if (k - 1 <= maxChanges) {
                minMoves = Math.min(minMoves, (long)2 * (k - 1));
            }
            // Option B: 2 originals P[i], P[i+1], k-2 changes
            if (i + 1 < m && k - 2 <= maxChanges) {
                long cost = oneIndices.get(i + 1) - oneIndices.get(i);
                minMoves = Math.min(minMoves, cost + (long)2 * (k - 2));
            }
            // Option C: 3 originals P[i-1], P[i], P[i+1], k-3 changes
            if (i > 0 && i + 1 < m && k - 3 <= maxChanges) {
                long cost = (long)oneIndices.get(i+1) - oneIndices.get(i-1);
                minMoves = Math.min(minMoves, cost + (long)2 * (k - 3));
            }
        }
        
        // If k is very small, we might not have enough original ones for the options above.
        // If k=1 and m>=1, cost is 0. If k=1 and m=0, cost is 2 (from initial minMoves).
        if (k > 0 && m >= k) { // If we can form k ones without changes
             long[] prefixSum = new long[m + 1];
             for (int i = 0; i < m; i++) {
                 prefixSum[i + 1] = prefixSum[i] + oneIndices.get(i);
             }
             for (int i = 0; i <= m - k; i++) {
                 minMoves = Math.min(minMoves, getGatherCost(prefixSum, oneIndices, i, i + k - 1));
             }
        }

        return minMoves;
    }

    private long getGatherCost(long[] prefixSum, List<Integer> oneIndices, int i, int j) {
        int w = j - i + 1;
        int medianIndexInWindow = (w - 1) / 2;
        int medianAbsIndex = i + medianIndexInWindow;
        
        long leftSum = prefixSum[medianAbsIndex] - prefixSum[i];
        long rightSum = prefixSum[j + 1] - prefixSum[medianAbsIndex + 1];
        long medianVal = oneIndices.get(medianAbsIndex);

        long cost = (medianIndexInWindow * medianVal - leftSum) + (rightSum - (long)(w - 1 - medianIndexInWindow) * medianVal);
        return cost;
    }
}

Note: The provided code snippet for the efficient approach is slightly simplified for clarity, focusing on the core idea of using small groups of 1, 2, or 3 original ones plus changes, which covers the most critical cases. A full implementation would combine this with the base case of using k original ones if maxChanges is 0.