Minimum Moves to Pick K Ones - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3086. Minimum Moves to Pick K Ones
Hard
50 Points
Array
Greedy
Sliding Window
Prefix Sum
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:
Return the minimum number of moves required by Alice to pick exactly k ones.
Examples
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 :
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 :
Constraints
2 <= n <= 105
0 <= nums[i] <= 1
1 <= k <= 105
0 <= maxChanges <= 105
maxChanges + sum(nums) >= k
3086. Minimum Moves to Pick K Ones
Hard
50 Points
Array
Greedy
Sliding Window
Prefix Sum
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:
Return the minimum number of moves required by Alice to pick exactly k ones.
Examples
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 :
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 :