PROBLEM LINK:
Author: Satyam Kumar
Tester: Parth Mittal
Editorialist: Rounaq Jhunjhunu Wala
DIFFICULTY:
EASY
PREREQUISITES:
Arrays
PROBLEM:
Given a filled array A and an empty array B, we need to copy the elements from A to B via the following two operations:
- Copy A[i] to B[i]
- Cyclic Shift B 1 position to the right (Shift b_i to b_{i+1} and b_n to b_1).
We need to minimize the number of operations to make the elements in B equal.
QUICK EXPLANATION:
Let us try to make all the elements of A equal to some x. Then, immediately, we can note that we will need to do at least N copy operations. Further, for all indices such that B_i \neq x, we need to move from the nearest i to its left. So the answer would be the maximum distance for that x + N. Now we take the minimum over all x. Since x is small, we can use an array of vectors.
EXPLANATION:
The question asks you to create the array B. The only thing we need to decide in the problem is the element in A which should be copied to B.
For choosing the element, we can devise the following method. We choose the maximum occurring element. But this might not give the optimal answer if the max occurring element is clustered at one place (because we would need to shift the array a lot more number of times).
A better strategy would be to pick an element, whose largest gap between copies is minimum. This comes from tha fact that the minimum (and required) number of copy operations is |A|, and hence we need to minimise the number of shift operations, which can be done for an element which doesn’t require much shifting. For example, if the array A = [1,2,1,1,2,1,3], we can see that the element 1 has a distance of maximum 1 between any copy, 2 has distance of maximum 3 (A_5 to A_2), and 3 is a lone element, so we can simply ignore it. Note that we also take wrap-around distances into account because the shift is cyclic. So in the above example, we get 1 as the best element, and we would do 7+1 operations to copy 1 to B.
Complexity: O(N)