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

oneof 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

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?

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`

.Time complexity

`O(n log max(A))`

.