Greedy algorithm - minimize number of operations to complete task

Question

I am trying to solve a programming challenge question. For convenience, I have summarized it below:

Given an array, A, of positive integers. In one operation, we can choose one of the elements in the array, A[i] and reduce it by a fixed amount X. At the same time, the rest of the elements will be reduced by a fixed amount Y. We need to find the minimum number of operations to reduce all elements to a non-positive number (i.e. 0 and below).

Constraints:
1 <= |A| <= 1e5
1 <= A[i] <= 1e9
1 <= Y < X <= 1e9
Time limit: 1 second

Source

For example, let X = 10, Y = 4 and A = {20, 20}.

The optimal approach for this example is:

Operation 1: Choose item 0.

A = {10, 16}

Operation 2: Choose item 0.

A = {0, 12}

Operation 3: Choose item 1.

A = {-4, 2}

Operation 4: Choose item 1.

A = {-8, -8}

Hence, the answer is 4.

---

My approach:

Keep choosing the current maximum element in the array and reduce it by X (and reduce the rest of the elements by Y). Clearly, this approach would exceed the time limit due to the possibly small values of X and Y (i.e. the number of iterations that my algorithm will perform is lower bounded by max(A[i]) / 2 ).

Could someone please advise me on a better solution?

Answer 1

This problem could be solved by using binary search

First, we want to check if within a operations, whether we can make all elements become <= 0; we could check for each element, the minimum number of operations, b, such that if we subtract x for b operations and subtract y for the remaining a-b operations, then the resultant value of the element will become <= 0. Sum all of those numbers together, and if the sum <= a, which means we could use a operations.

Then, we could apply binary search to search for a valid a.

int st = 0;
int ed = max element / y + 1;
int result = ed;
while(start <= end){
    int mid = (st + ed)/2;
    int sum = 0;
    for(int i : A){
        sum += minTimesMinusX(i, mid);
    }
    if(sum <= mid){
        result = mid;
        ed = mid - 1;
    }else{
        st = mid + 1;
    }
}
return result;

Time complexity O(n log max(A)).