Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript

• 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;
  }
  
  

All Problems

All Solutions