We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Moves to Pick K Ones

Number: 3327

Difficulty: Hard

Paid? No

Companies: TikTok

Problem Description

Given a binary array nums, an integer k and a limit maxChanges on the number of allowed bit‐flips, Alice wants to “pick up” exactly k ones using the minimum number of moves. When the game begins, she may choose any index (called aliceIndex) from 0 to n–1. If nums[aliceIndex] is 1 then that one is picked instantly (and the cell becomes 0) without consuming a move. Afterwards, in each move she can perform exactly one of the following actions: • Pick any index j (j != aliceIndex) with nums[j] == 0 and change it to 1. This “flip” action can be used at most maxChanges times. • Pick two adjacent indices x and y (|x – y| == 1) with nums[x] == 1 and nums[y] == 0, and swap them – that is, set nums[y] = 1 and nums[x] = 0. If y equals aliceIndex then the one arriving there is immediately “picked up” (and that cell becomes 0). Return the minimum number of moves required to achieve exactly k ones picked up.

Key Insights

  • The allowed operations create a “transport” mechanism where ones are moved via adjacent swaps toward a chosen starting position.
  • Flips (which cost one move each) can create ones arbitrarily (subject to maxChanges), but note that after a flip a swap is needed to bring the new one next to aliceIndex (thus effectively costing 2 moves per flip‐created one).
  • For ones that already exist in nums, the cost of “bringing” one from position i to aliceIndex is the distance |i – aliceIndex|. Choosing aliceIndex optimally (in practice, at the median location of a chosen block of ones) minimizes the sum of distances.
  • One may decide to pick up some ones from the original array and “create” the remainder via flips. Thus the solution is to try all splits where i real ones are used (from a contiguous block) and k–i ones come from flips (at cost 2 each).
  • To quickly compute the total “swap cost” for any contiguous block of ones (by aligning them around its median), a prefix sum over the indices of ones is used.

Space and Time Complexity

Time Complexity: O(n) if we precompute the positions and prefix sums and then scan through all possible contiguous blocks of real ones. Space Complexity: O(n) to store the positions of ones and the prefix-sum array.

Solution

The idea is to first collect the indices of the ones already in nums into an array (call it ones). Note that by performing at most maxChanges flips we can produce a total of (original ones count + maxChanges) ones, which is guaranteed to be at least k. Then, we consider splitting the required k ones into two groups:

  1. i ones taken from the original ones (for which we must “move” them to the chosen starting point using adjacent swaps).
  2. k – i ones that we create via flips; each such one will cost 2 moves (one for the flip and one for swapping it to aliceIndex).

For a contiguous block of i ones taken from the array ones, the best strategy is to choose aliceIndex equal to the median of those positions, because this minimizes the total swap cost, which is the sum of the absolute differences between each one’s position and the median. This sum can be computed in O(1) per block by precomputing a prefix sum of the ones array. We do this for each possible contiguous block of i ones (for all valid i) and take the minimum overall cost. Also, we consider the possibility of using only flips (i.e. i == 0) if k is not larger than maxChanges. Finally, we output the minimum moves found.

A few gotchas: • Be cautious with the adjustment for a block’s median: for a block starting at index s with length i, let m = s + i//2 be its median. Then, using the prefix sum array, the cost is computed as:   cost = (ones[m](m – s) – (prefix[m–1] – (prefix[s–1] if s > 0 else 0))) + ((prefix[s+i–1] – prefix[m]) – ones[m]((s+i–1) – m)) • Remember that the one at aliceIndex (i.e. the median) is “picked up” without any swap cost. • When creating ones by flips, note that even though a flip costs 1 move, an extra swap move is necessary to move the newly created one next to aliceIndex, totalling 2 moves per flip‐created one.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java. Each solution uses clear variable names and line‐by‐line comments.

def minMoves(nums, k, maxChanges):
    # Collect positions of ones
    ones = [i for i, val in enumerate(nums) if val == 1]
    nones = len(ones)
    INF = float('inf')
    
    # Precompute prefix sums for ones positions for quick cost computation
    prefix = [0] * nones
    for i, pos in enumerate(ones):
        prefix[i] = pos if i == 0 else prefix[i-1] + pos
    
    # Function to compute cost to align a block of ones to its median
    # Block: ones[s] to ones[s + len_block - 1]
    def blockCost(s, len_block):
        m = s + len_block // 2  # median index in the block
        median = ones[m]
        # Left cost: cost to bring ones from s to m to median
        left_cost = 0
        if m > s:
            # sum of differences from median for left part
            left_sum = prefix[m-1] - (prefix[s-1] if s > 0 else 0)
            left_cost = median*(m - s) - left_sum
        # Right cost: cost to bring ones from m+1 to s+len_block-1 to median
        right_cost = 0
        if m < s + len_block - 1:
            right_sum = (prefix[s+len_block-1] - prefix[m])
            right_cost = right_sum - median*((s+len_block-1) - m)
        return left_cost + right_cost
    
    min_moves = INF
    
    # Option 1: Use only flips, if allowed.
    if k <= maxChanges:
        # Each flip costs 1 move and then a swap of 1 move ==> 2 moves per created one.
        min_moves = min(min_moves, 2 * k)
    
    # Option 2: Use i real ones and (k - i) ones by flips.
    # We must use at least max(1, k - maxChanges) real ones because we cannot flip more than maxChanges ones.
    start_real = max(1, k - maxChanges)  # at least one real one because we can have a free pick at aliceIndex
    end_real = min(k, nones)  # Cannot use more real ones than available, and total real ones used is at most k
    for real_count in range(start_real, end_real + 1):
        # For each contiguous block of length real_count in ones, compute the cost.
        local_min = INF
        # Slide over all possible contiguous blocks of real_count ones
        for s in range(0, nones - real_count + 1):
            cost_moves = blockCost(s, real_count)
            if cost_moves < local_min:
                local_min = cost_moves
        # Total cost = moves to transport real ones + cost for flips (2 moves each)
        total_cost = local_min + 2 * (k - real_count)
        if total_cost < min_moves:
            min_moves = total_cost
    return min_moves

# Example usage:
nums1 = [1,1,0,0,0,1,1,0,0,1]
print(minMoves(nums1, 3, 1))  # Expected output: 3
nums2 = [0,0,0,0]
print(minMoves(nums2, 2, 3))  # Expected output: 4
← Back to All Questions