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]
byx
. - Decrement values by
y
at all indices except theith
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|