# PROBLEM LINK:

Practice

Contest

**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 `vector`

s.

# 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)$

asked
**12 Oct '16, 22:23**

2★rounaqwl66

26●3

accept rate:
25%