# 3086. Minimum Moves to Pick K Ones

## Description

You are given a binary array nums of length n, a positive integer k and a non-negative integer maxChanges.

Alice plays a game, where the goal is for Alice to pick up k ones from nums using the minimum number of moves. When the game starts, Alice picks up any index aliceIndex in the range [0, n - 1] and stands there. If nums[aliceIndex] == 1 , Alice picks up the one and nums[aliceIndex] becomes 0(this does not count as a move). After this, Alice can make any number of moves (including zero) where in each move Alice must perform exactly one of the following actions:

• Select any index j != aliceIndex such that nums[j] == 0 and set nums[j] = 1. This action can be performed at most maxChanges times.
• Select any two adjacent indices x and y (\|x - y\| == 1) such that nums[x] == 1, nums[y] == 0, then swap their values (set nums[y] = 1 and nums[x] = 0). If y == aliceIndex, Alice picks up the one after this move and nums[y] becomes 0.

Return the minimum number of moves required by Alice to pick exactly k ones.

Example 1:

Input: nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1

Output: 3

Explanation: Alice can pick up 3 ones in 3 moves, if Alice performs the following actions in each move when standing at aliceIndex == 1:

•  At the start of the game Alice picks up the one and nums[1] becomes 0. nums becomes [1,1,1,0,0,1,1,0,0,1].
• Select j == 2 and perform an action of the first type. nums becomes [1,0,1,0,0,1,1,0,0,1]
• Select x == 2 and y == 1, and perform an action of the second type. nums becomes [1,1,0,0,0,1,1,0,0,1]. As y == aliceIndex, Alice picks up the one and nums becomes [1,0,0,0,0,1,1,0,0,1].
• Select x == 0 and y == 1, and perform an action of the second type. nums becomes [0,1,0,0,0,1,1,0,0,1]. As y == aliceIndex, Alice picks up the one and nums becomes [0,0,0,0,0,1,1,0,0,1].

Note that it may be possible for Alice to pick up 3 ones using some other sequence of 3 moves.

Example 2:

Input: nums = [0,0,0,0], k = 2, maxChanges = 3

Output: 4

Explanation: Alice can pick up 2 ones in 4 moves, if Alice performs the following actions in each move when standing at aliceIndex == 0:

• Select j == 1 and perform an action of the first type. nums becomes [0,1,0,0].
• Select x == 1 and y == 0, and perform an action of the second type. nums becomes [1,0,0,0]. As y == aliceIndex, Alice picks up the one and nums becomes [0,0,0,0].
• Select j == 1 again and perform an action of the first type. nums becomes [0,1,0,0].
• Select x == 1 and y == 0 again, and perform an action of the second type. nums becomes [1,0,0,0]. As y == aliceIndex, Alice picks up the one and nums becomes [0,0,0,0].

Constraints:

• 2 <= n <= 105
• 0 <= nums[i] <= 1
• 1 <= k <= 105
• 0 <= maxChanges <= 105
• maxChanges + sum(nums) >= k

## Solutions

### Solution 1

• class Solution {
public long minimumMoves(int[] nums, int k, int maxChanges) {
int n = nums.length;
int[] cnt = new int[n + 1];
long[] s = new long[n + 1];
for (int i = 1; i <= n; ++i) {
cnt[i] = cnt[i - 1] + nums[i - 1];
s[i] = s[i - 1] + i * nums[i - 1];
}
long ans = Long.MAX_VALUE;
for (int i = 1; i <= n; ++i) {
long t = 0;
int need = k - nums[i - 1];
for (int j = i - 1; j <= i + 1; j += 2) {
if (need > 0 && 1 <= j && j <= n && nums[j - 1] == 1) {
--need;
++t;
}
}
int c = Math.min(need, maxChanges);
need -= c;
t += c * 2;
if (need <= 0) {
ans = Math.min(ans, t);
continue;
}
int l = 2, r = Math.max(i - 1, n - i);
while (l <= r) {
int mid = (l + r) >> 1;
int l1 = Math.max(1, i - mid), r1 = Math.max(0, i - 2);
int l2 = Math.min(n + 1, i + 2), r2 = Math.min(n, i + mid);
int c1 = cnt[r1] - cnt[l1 - 1];
int c2 = cnt[r2] - cnt[l2 - 1];
if (c1 + c2 >= need) {
long t1 = 1L * c1 * i - (s[r1] - s[l1 - 1]);
long t2 = s[r2] - s[l2 - 1] - 1L * c2 * i;
ans = Math.min(ans, t + t1 + t2);
r = mid - 1;
} else {
l = mid + 1;
}
}
}
return ans;
}
}

• class Solution {
public:
long long minimumMoves(vector<int>& nums, int k, int maxChanges) {
int n = nums.size();
vector<int> cnt(n + 1, 0);
vector<long long> s(n + 1, 0);

for (int i = 1; i <= n; ++i) {
cnt[i] = cnt[i - 1] + nums[i - 1];
s[i] = s[i - 1] + 1LL * i * nums[i - 1];
}

long long ans = LLONG_MAX;

for (int i = 1; i <= n; ++i) {
long long t = 0;
int need = k - nums[i - 1];

for (int j = i - 1; j <= i + 1; j += 2) {
if (need > 0 && 1 <= j && j <= n && nums[j - 1] == 1) {
--need;
++t;
}
}

int c = min(need, maxChanges);
need -= c;
t += c * 2;

if (need <= 0) {
ans = min(ans, t);
continue;
}

int l = 2, r = max(i - 1, n - i);

while (l <= r) {
int mid = (l + r) / 2;
int l1 = max(1, i - mid), r1 = max(0, i - 2);
int l2 = min(n + 1, i + 2), r2 = min(n, i + mid);

int c1 = cnt[r1] - cnt[l1 - 1];
int c2 = cnt[r2] - cnt[l2 - 1];

if (c1 + c2 >= need) {
long long t1 = 1LL * c1 * i - (s[r1] - s[l1 - 1]);
long long t2 = s[r2] - s[l2 - 1] - 1LL * c2 * i;
ans = min(ans, t + t1 + t2);
r = mid - 1;
} else {
l = mid + 1;
}
}
}

return ans;
}
};

• class Solution:
def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:
n = len(nums)
cnt = [0] * (n + 1)
s = [0] * (n + 1)
for i, x in enumerate(nums, 1):
cnt[i] = cnt[i - 1] + x
s[i] = s[i - 1] + i * x
ans = inf
max = lambda x, y: x if x > y else y
min = lambda x, y: x if x < y else y
for i, x in enumerate(nums, 1):
t = 0
need = k - x
for j in (i - 1, i + 1):
if need > 0 and 1 <= j <= n and nums[j - 1] == 1:
need -= 1
t += 1
c = min(need, maxChanges)
need -= c
t += c * 2
if need <= 0:
ans = min(ans, t)
continue
l, r = 2, max(i - 1, n - i)
while l <= r:
mid = (l + r) >> 1
l1, r1 = max(1, i - mid), max(0, i - 2)
l2, r2 = min(n + 1, i + 2), min(n, i + mid)
c1 = cnt[r1] - cnt[l1 - 1]
c2 = cnt[r2] - cnt[l2 - 1]
if c1 + c2 >= need:
t1 = c1 * i - (s[r1] - s[l1 - 1])
t2 = s[r2] - s[l2 - 1] - c2 * i
ans = min(ans, t + t1 + t2)
r = mid - 1
else:
l = mid + 1
return ans

• func minimumMoves(nums []int, k int, maxChanges int) int64 {
n := len(nums)
cnt := make([]int, n+1)
s := make([]int, n+1)

for i := 1; i <= n; i++ {
cnt[i] = cnt[i-1] + nums[i-1]
s[i] = s[i-1] + i*nums[i-1]
}

ans := math.MaxInt64

for i := 1; i <= n; i++ {
t := 0
need := k - nums[i-1]

for _, j := range []int{i - 1, i + 1} {
if need > 0 && 1 <= j && j <= n && nums[j-1] == 1 {
need--
t++
}
}

c := min(need, maxChanges)
need -= c
t += c * 2

if need <= 0 {
ans = min(ans, t)
continue
}

l, r := 2, max(i-1, n-i)

for l <= r {
mid := (l + r) >> 1
l1, r1 := max(1, i-mid), max(0, i-2)
l2, r2 := min(n+1, i+2), min(n, i+mid)

c1 := cnt[r1] - cnt[l1-1]
c2 := cnt[r2] - cnt[l2-1]

if c1+c2 >= need {
t1 := c1*i - (s[r1] - s[l1-1])
t2 := s[r2] - s[l2-1] - c2*i
ans = min(ans, t+t1+t2)
r = mid - 1
} else {
l = mid + 1
}
}
}

return int64(ans)
}

• function minimumMoves(nums: number[], k: number, maxChanges: number): number {
const n = nums.length;
const cnt = Array(n + 1).fill(0);
const s = Array(n + 1).fill(0);

for (let i = 1; i <= n; i++) {
cnt[i] = cnt[i - 1] + nums[i - 1];
s[i] = s[i - 1] + i * nums[i - 1];
}

let ans = Infinity;
for (let i = 1; i <= n; i++) {
let t = 0;
let need = k - nums[i - 1];

for (let j of [i - 1, i + 1]) {
if (need > 0 && 1 <= j && j <= n && nums[j - 1] === 1) {
need--;
t++;
}
}

const c = Math.min(need, maxChanges);
need -= c;
t += c * 2;

if (need <= 0) {
ans = Math.min(ans, t);
continue;
}

let l = 2,
r = Math.max(i - 1, n - i);

while (l <= r) {
const mid = (l + r) >> 1;
const [l1, r1] = [Math.max(1, i - mid), Math.max(0, i - 2)];
const [l2, r2] = [Math.min(n + 1, i + 2), Math.min(n, i + mid)];

const c1 = cnt[r1] - cnt[l1 - 1];
const c2 = cnt[r2] - cnt[l2 - 1];

if (c1 + c2 >= need) {
const t1 = c1 * i - (s[r1] - s[l1 - 1]);
const t2 = s[r2] - s[l2 - 1] - c2 * i;
ans = Math.min(ans, t + t1 + t2);
r = mid - 1;
} else {
l = mid + 1;
}
}
}

return ans;
}