This is a reiteration of the official Editorial supported with code. Link to Problem — Combination Lock. I would suggest you to read the original problem statement first before going through this editorial.
Problem
Your are given an array of numbers of length W and an integer N. Each number of array, let’s say is in range . In one move you can select any number from the array and increase/decrease that number by 1, wrapping around between 1 and N. For example, let’s N=6, and we choose 6. If we increase it should wrap around to 1. Similarly, if 1 is decreased, it becomes 6.
You need to find the minimum number of moves to make all elements of array equal. Constraints
A Brute Force Solution
Observation 1: The moves performed at any index/position in the array is independent of moves performed at any other position.
If we choose a target value T and we want each element to be equal to T, then the moves we perform at any position in array won’t affect moves performed at other positions. Thus, the number of moves at every position can be calculated separately. There are N possible values of T i.e 1 <= T <= N.
Observation 2: There are two possible ‘number of moves’ for a value X to reach T. If T >= X, they are: T — X and N — (T — X). If X >= T then X — T and N — (X — T).
Using above two observation we can construct the brute force solution as
Time complexity of this approach is: O(N * W). We are performing W operations for each value of N.
Unfortunately, this is not sufficient to pass the given constraints.
Continue, if you have properly understood the brute force solution.
Improvement of the brute force solution
Observation 3: A major observation is that we can get the minimum possible moves by bringing all the array values to one of the initial values of the array.
Proof
First let’s sort the array. Now, consider a value val that is not equal to any of the initial values of array and we want val to be the target value. Also, consider two numbers from the initial array: and such that X i is the last number smaller than val and X j is the first number larger than val.
To optimally reach val each number from initial array has to first reach X i or X j. After performing those operations, let n 1 numbers are at X i and n 2 numbers are at X j. Then the final number of moves for all numbers to reach val would be equal to:
.
We can show that this can always be improved by shifting val to either X i or X j
- If n1 < n2 then we can shift val to Xj and the number of operations would become . We are transforming numbers at Xi to value Xj. The numbers at Xj are already at correct place so no operations for them. Similarly,
- If n2 <= n1 then we can shift val to Xi and the number of operations would become
If you compare then in both cases we have lesser number operations than keeping val unchanged.
The Optimal Solution
So, now we know that the target value is one of the intial values of the array.
Remember that the array is sorted.
Observation 4: Consider, one of the initial values as target value T and two numbers X1 and X2 such that X1 < X2 <= T. Then, it is never possible that X1 reaches T by performing increment operations only and X2 reaches T by performing decrement operations only. If the optimal way for X1 to reach T is by perfoming increment operations then X2 would also prefer increasing as it closer to T than X1.
So, from this we can also conclude that -
- There exists some position i, 0 <= i <= t such that for all j, 0 <= j < i values at position j prefer decreasing and for all k, i <= k <= t would prefer increasing.
- There exists some position u, t <= u < W such that for all v, t <= v <= u values at position v prefer decreasing and for all w, u < w < W would prefer increasing.
t is the index of T. We can binary search for i and u for every t we choose.
Let’s see how to find i for certain t. u can be found similarly.
Consider the following scenerio. We know that i is in range [0, t]. Consider mid point of this range let’s say x.
If, T-arr[x] > N - (T-arr[x]) this means that value at x will increase to reach T. This also means that all positions greater than x would also prefer increasing.
So, from this we can say that either i = x or i < x and we can omit the range [x, t]. We have omitted exactly half of the range which is the essence behind Binary Search. We proceed similarly with the other half until i is found. (See code for implementation details)
Now, let’s calculate total moves once we know i and u.
Let’s also assume that we have a function getSum(m, n) which returns arr[m] + arr[m+1] … arr[n] i.e sum of all numbers from postion m to n (inclusive). Extending on the above points we have
Similarly,
Thus the total moves for target value T at position t denoted by sum is,sum = sum1 + sum2 + sum3 + sum4
Also, getSum(m, n) = prefixSum[n] — prefixSum[m-1]
where, prefix[x] is the sum of elements with index less than equal to x. We can preprocess and store prefix[x] to achive a constant time operation to calculate sum.
So, we calculate sum for all possible initial values and take minimum of them which is the answer.
Time complexity of this solution is: O(W * log W)
For implementation visit: https://hold7door.github.io/panacea/google-kickstart-2020-round-g/
Originally published at https://hold7door.github.io.
