Welcome to Subscribe On Youtube

2702. Minimum Operations to Make Numbers Non-positive

Description

You are given a 0-indexed integer array nums and two integers x and y. In one operation, you must choose an index i such that 0 <= i < nums.length and perform the following:

• Decrement nums[i] by x.
• Decrement values by y at all indices except the ith one.

Return the minimum number of operations to make all the integers in nums less than or equal to zero.

 

Example 1:

Input: nums = [3,4,1,7,6], x = 4, y = 2
Output: 3
Explanation: You will need three operations. One of the optimal sequence of operations is:
Operation 1: Choose i = 3. Then, nums = [1,2,-1,3,4]. 
Operation 2: Choose i = 3. Then, nums = [-1,0,-3,-1,2].
Operation 3: Choose i = 4. Then, nums = [-3,-2,-5,-3,-2].
Now, all the numbers in nums are non-positive. Therefore, we return 3.

Example 2:

Input: nums = [1,2,1], x = 2, y = 1
Output: 1
Explanation: We can perform the operation once on i = 1. Then, nums becomes [0,0,0]. All the positive numbers are removed, and therefore, we return 1.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= y < x <= 109

Solutions

Solution 1: Binary Search

We notice that if an operation count $t$ can make all numbers less than or equal to $0$, then for any $t’ > t$, the operation count $t’$ can also make all numbers less than or equal to $0$. Therefore, we can use binary search to find the minimum operation count.

We define the left boundary of the binary search as $l=0$, and the right boundary as $r=\max(nums)$. Each time we perform a binary search, we find the middle value $mid=\lfloor\frac{l+r}{2}\rfloor$, and then determine whether there exists an operation method that does not exceed $mid$ and makes all numbers less than or equal to $0$. If it exists, we update the right boundary $r = mid$, otherwise, we update the left boundary

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

• class Solution {
      private int[] nums;
      private int x;
      private int y;
  
      public int minOperations(int[] nums, int x, int y) {
          this.nums = nums;
          this.x = x;
          this.y = y;
          int l = 0, r = 0;
          for (int v : nums) {
              r = Math.max(r, v);
          }
          while (l < r) {
              int mid = (l + r) >>> 1;
              if (check(mid)) {
                  r = mid;
              } else {
                  l = mid + 1;
              }
          }
          return l;
      }
  
      private boolean check(int t) {
          long cnt = 0;
          for (int v : nums) {
              if (v > (long) t * y) {
                  cnt += (v - (long) t * y + x - y - 1) / (x - y);
              }
          }
          return cnt <= t;
      }
  }
  

• class Solution {
  public:
      int minOperations(vector<int>& nums, int x, int y) {
          int l = 0, r = *max_element(nums.begin(), nums.end());
          auto check = [&](int t) {
              long long cnt = 0;
              for (int v : nums) {
                  if (v > 1LL * t * y) {
                      cnt += (v - 1LL * t * y + x - y - 1) / (x - y);
                  }
              }
              return cnt <= t;
          };
          while (l < r) {
              int mid = (l + r) >> 1;
              if (check(mid)) {
                  r = mid;
              } else {
                  l = mid + 1;
              }
          }
          return l;
      }
  };
  

• class Solution:
      def minOperations(self, nums: List[int], x: int, y: int) -> int:
          def check(t: int) -> bool:
              cnt = 0
              for v in nums:
                  if v > t * y:
                      cnt += ceil((v - t * y) / (x - y))
              return cnt <= t
  
          l, r = 0, max(nums)
          while l < r:
              mid = (l + r) >> 1
              if check(mid):
                  r = mid
              else:
                  l = mid + 1
          return l
  
  

• func minOperations(nums []int, x int, y int) int {
  	var l, r int
  	for _, v := range nums {
  		r = max(r, v)
  	}
  	check := func(t int) bool {
  		cnt := 0
  		for _, v := range nums {
  			if v > t*y {
  				cnt += (v - t*y + x - y - 1) / (x - y)
  			}
  		}
  		return cnt <= t
  	}
  	for l < r {
  		mid := (l + r) >> 1
  		if check(mid) {
  			r = mid
  		} else {
  			l = mid + 1
  		}
  	}
  	return l
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

• function minOperations(nums: number[], x: number, y: number): number {
      let l = 0;
      let r = Math.max(...nums);
      const check = (t: number): boolean => {
          let cnt = 0;
          for (const v of nums) {
              if (v > t * y) {
                  cnt += Math.ceil((v - t * y) / (x - y));
              }
          }
          return cnt <= t;
      };
      while (l < r) {
          const mid = (l + r) >> 1;
          if (check(mid)) {
              r = mid;
          } else {
              l = mid + 1;
          }
      }
      return l;
  }
  
  

All Problems

All Solutions