New task for your interview prep

We are given an array of integers of size N and also a number X. We need to find such a number Y that the expression

min(a[0], Y) + min(a[1], Y) + … + min(a[N-1], Y)

is as close to X as possible.

Time complexity: O(N)

Solution

Linear reduction means linear solution

Let’s digress a bit and talk in general about linear reduction. It’s when you can reduce the task in O(N) time with input of size N to the same task, but with input of smaller size N / 2. In that case, you can solve the whole task in O(N) time. Let’s figure out why.

If you can reduce in O(N) time, that means there exists such constant number k that the reduction time is < k * N. Let’s spend k * N time and perform one reduction. Now we have the same task, but with the input size N / 2. Now let’s perform another reduction, spending k * (N / 2) time. Now we have input of size N / 4. And we continue going on like that. In the end, we reduce the initial task to size 1 and solve it.

The overall amount of time spent is

k*N + k * N / 2 + k * N / 4 + … + k = k * (2N -1) < 2k * N

That means that the whole solution is linear.

This fact greatly simplifies all linear tasks. Now we do not have to solve the entire task, we just need to be able to reduce it to the same smaller task in linear time.

Making things more complicated

If we want to use reduction, then we must be aware that not all problems are actually reducible, i.e. not all problems can be reduced to the same problem but with smaller input size.

To make a problem reducible, sometimes we need to make it more complicated.

For instance, instead of solving our initial task, we will solve more complicated task: given the array and the numbers X and Z, we need to find such Y that

abs(min(a[0], Y) + min(a[1], Y) + … + min(a[N-1], Y) + Y * Z-X) -> min.

If we can solve this task, we can solve the original task by simply putting Z = 0 for the original task.

How to reduce

Now we need to solve the task of finding Y such that

abs(min(a[0], Y) + min(a[1], Y) + … + min(a[N-1], Y) + Y * Z -X) -> min.

But we will not go into fully solving it, but instead we will just reduce it to the same task of size N / 2.

Let’s find a median M of the array a. Median is such a number that exactly N / 2 elements of the array are smaller than M, and exactly N / 2 elements are bigger than M. This could be done with O(N) time (you can read how to do this, for example, here).

After that, we need to question if the potential best Y is > M or < M. For this, we are going to compute

min(a[0], M) + min(a[1], M) + … + min(a[N -1], M) + M * Z and compare it with X.

1. If this expression is > X, then we need to have Y < M to make the expression closer to X.
2. If this expression is < X, then we need to have Y > M to make the expression closer to X.
3. If this expression = X, then we have already found the best Y, Y = M.

Let’s understand in detail what we do in each subcase.

Reduction in subcase 1

If the expression above is > X, we need to find ideal Y and we know it is < M. What do we do about it? We notice that if some a[k] >= M, then a[k] >= M > Y, therefore for the ideal Y we have

min(a[k], Y) = Y.

In that case, let’s in O(N) time compute indices k_i such that a[k_i] < M. Let’s also compute the count of all other indices K such that a[k] >= M.

Then min(a[0], Y) + min(a[1], Y) + … + min(a[N-1], Y) + Y * Z =min(a[k_1], Y) + min(a[k_2], Y) + … + min(a[k_(N/2)], Y) + K * Y + Y * Z =min(a[k_1], Y) + min(a[k_2], Y) + … + min(a[k_(N/2)], Y) + Y * (K + Z)

So now we need to solve the task

abs(min(a[k_1], Y) + min(a[k_2], Y) + … + min(a[k_(N/2)], Y) +

+ Y * (K + Z)-X) — > min.

This is the same task as before, but with K + Z instead of Z, and the size of the array is now N / 2. So we successfully reduced the task to the same task but of size N / 2.

Reduction in subcase 2

We need to analyze another case when the expression

min(a[0], M) + min(a[1], M) + … + min(a[N-1], M) + M * Z < X

If the expression is < X, that means that ideal Y should be > M.

That means that for all elements for which a[k] <= M it is true that a[k] <= M < Y, so

min(a[k], Y) = a[k].

Let’s in linear time O(N) find all such indices d_i, such that a[d_i] > M. Let’s find the sum S of all elements a[k] that are <= M.

Then we have

min(a[0], Y) + min(a[1], Y) + … + min(a[N-1], Y) + Y * Z =min(a[d_1], Y) + min(a[d_2], Y) + … + min(a[d_(N/2)], Y) + S + Y * Z

So now we have to solve the task

abs(min(a[d_1], Y) + min(a[d_2], Y) + … + min(a[d_(N/2)], Y) + S + Y * Z -X) — > min

It is the same as

abs(min(a[d_1], Y) + min(a[d_2], Y) + … + min(a[d_(N/2)], Y) + Y * Z -(X-S)) — > min

So we again successfully reduced the task to the same task, but with size N / 2 and number X -S instead of number X.

In all the cases, we were able to spend O(N) time and reduce the task to the same task but of size N / 2. That means that we are able to solve the whole task in O(N) time.