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
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
.
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))
.