Problem

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 innums less than or equal to zero.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

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 <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= y < x <= 10^9

Solution

Method 1 – Greedy & Binary Search

Intuition

Each operation reduces one element by x and all others by y. The optimal strategy is to perform the operation on the largest element, as it benefits most from the larger decrement. We can use binary search to find the minimum number of operations needed so that all elements become non-positive.

Approach

  1. Use binary search for the answer (number of operations).
  2. For each guess, check if there exists a way to choose indices such that all elements are <= 0 after that many operations.
  3. For each element, the number of times it must be chosen is at least ceil((nums[i] - ops * y) / (x - y)), but not more than ops.
  4. If the sum of required choices is <= ops, it’s possible.
  5. Edge case: If all elements are already non-positive, answer is 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int minOperations(vector<int>& nums, int x, int y) {
        int n = nums.size();
        int l = 0, r = *max_element(nums.begin(), nums.end()) / y + 2;
        auto check = [&](int ops) {
            long long need = 0;
            for (int v : nums) {
                long long left = v - 1LL * ops * y;
                if (left > 0) need += (left + (x - y - 1)) / (x - y);
            }
            return need <= ops;
        };
        while (l < r) {
            int m = (l + r) / 2;
            if (check(m)) r = m;
            else l = m + 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

func minOperations(nums []int, x, y int) int {
    l, r := 0, 0
    for _, v := range nums {
        if v/y+2 > r { r = v/y + 2 }
    }
    check := func(ops int) bool {
        need := 0
        for _, v := range nums {
            left := v - ops*y
            if left > 0 {
                need += (left + (x-y-1)) / (x-y)
            }
        }
        return need <= ops
    }
    for l < r {
        m := (l + r) / 2
        if check(m) {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int minOperations(int[] nums, int x, int y) {
        int l = 0, r = 0;
        for (int v : nums) r = Math.max(r, v / y + 2);
        while (l < r) {
            int m = (l + r) / 2;
            long need = 0;
            for (int v : nums) {
                long left = v - 1L * m * y;
                if (left > 0) need += (left + (x - y - 1)) / (x - y);
            }
            if (need <= m) r = m;
            else l = m + 1;
        }
        return l;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minOperations(nums: IntArray, x: Int, y: Int): Int {
        var l = 0
        var r = nums.maxOrNull()!! / y + 2
        while (l < r) {
            val m = (l + r) / 2
            var need = 0L
            for (v in nums) {
                val left = v - m * y
                if (left > 0) need += (left + (x - y - 1)) / (x - y)
            }
            if (need <= m) r = m else l = m + 1
        }
        return l
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def minOperations(self, nums: list[int], x: int, y: int) -> int:
        l, r = 0, max(nums) // y + 2
        while l < r:
            m = (l + r) // 2
            need = 0
            for v in nums:
                left = v - m * y
                if left > 0:
                    need += (left + (x - y - 1)) // (x - y)
            if need <= m:
                r = m
            else:
                l = m + 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

impl Solution {
    pub fn min_operations(nums: Vec<i32>, x: i32, y: i32) -> i32 {
        let mut l = 0;
        let mut r = nums.iter().max().unwrap() / y + 2;
        while l < r {
            let m = (l + r) / 2;
            let mut need = 0;
            for &v in &nums {
                let left = v - m * y;
                if left > 0 {
                    need += (left + (x - y - 1)) / (x - y);
                }
            }
            if need <= m {
                r = m;
            } else {
                l = m + 1;
            }
        }
        l
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    minOperations(nums: number[], x: number, y: number): number {
        let l = 0, r = Math.max(...nums) / y + 2;
        while (l < r) {
            const m = Math.floor((l + r) / 2);
            let need = 0;
            for (const v of nums) {
                const left = v - m * y;
                if (left > 0) need += Math.floor((left + (x - y - 1)) / (x - y));
            }
            if (need <= m) r = m;
            else l = m + 1;
        }
        return l;
    }
}

Complexity

  • ⏰ Time complexity: O(n log(max(nums)/y)) — Binary search for the answer, each check is O(n).
  • 🧺 Space complexity: O(1) — Only a few variables are used, no extra space proportional to input size.