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 <= 1051 <= nums[i] <= 1091 <= 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
| 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
|
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
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func minOperations(nums []int, x int, y int) int {
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
}
l, r := 0, slices.Max(nums)
for l < r {
mid := (l + r) >> 1
if check(mid) {
r = mid
} else {
l = mid + 1
}
}
return l
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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;
}
|
