1
$\begingroup$

I've been stuck on this problem for some time now..

Given an array A of size N that ranges between [1..N], a "move" is to increase or decrease an element (by 1). After each move the array must remain within [1..N]

I need to find the minimum number of move operations to make the array pairwise distinct.

$\endgroup$
5
$\begingroup$

First Observation:
Consider the result array, which contains $N$ distinct numbers between 1 and $N$.
Since there are only $N$ numbers between 1 and $N$, all those numbers must appear in the result array and no other numbers will appear.

Second Observation:
Consider $1$, the smallest number in the result array. Which number in $A$ should be changed to $1$ so as to incur the least cost? The smallest number of $A$.
Then consider $2$, the next smallest number in the result array. Which number among the remaining numbers in $A$ should be changed to $2$ so as to incur the least cost? The smallest of the remaining numbers in $A$.
Then consider $3$, the next smallest number in the result array. Which number among the remaining numbers in $A$ should be changed to $3$ so as to incur the least cost? The smallest of the remaining numbers in $A$.
And so on.
That is, we should change the $k$-th smallest number in the original array to $k$.

So, the algorithm is

  1. sort $A$.
  2. return the sum of $|A[i]-i|$, with $i$ ranging over $1..N$, assuming $A$ is 1-indexed.

Exercise. Given four numbers $a_1\le a_2$ and $b_1\le b_2$, prove $$|a_1-b_1| + |a_2-b_2| \le |a_1-b_2| + |a_2-b_1|.$$

$\endgroup$
2
  • $\begingroup$ What's the goal of the exercise ?? $\endgroup$ – droptop May 30 at 19:02
  • 3
    $\begingroup$ To help prove the algorithm is correct mathematically. $\endgroup$ – John L. May 30 at 20:48
1
$\begingroup$

Consider an array of all $1$'s. Then, the number of increments required (no decrements are required) is exactly

\begin{equation}\sum_{i=1}^{N-1} i\end{equation}

This value is known to be equal to $\frac{N(N-1)}{2}=\Theta(N^2)$

Additionally, every array with size $N$ you can transform to be pair-wise distinct with $O(N^2)$ operations, so this value is the optimal possible number of operations required.

$\endgroup$
2
  • $\begingroup$ While this gives an upper bound on the number of moves needed in the worst case, I don’t see how to adapt it into a general algorithm for calculating the number of moves for an arbitrary array. $\endgroup$ – templatetypedef May 30 at 16:21
  • 1
    $\begingroup$ @templatetypedef the OP didn't specify he wanted an algorithm to calculate this. Usually when you consider a problem and ask "how much time do I need to solve this" \ "how many operations do I need to solve this" - it means in the worst case, how much do we need to "pay". If the OP wanted an algorithm to calculate this for any specific array, it would be a different question and would be specified directly. $\endgroup$ – nir shahar May 30 at 16:30
1
$\begingroup$

Here’s one possible approach that frames the problem as a minimum-cost bipartite matching. You know that each number in the array must end up holding one of the values from $1$ to $N$, and that no two numbers can get the same value. Therefore, you’re looking to assign the sequence $1, 2, \dots, N$ to the initial values in the array. And in particular, the cost of incrementing or decrementing the initial value $i$ to a target value $j$ is $|i - j|$. So construct a complete bipartite graph where one set of nodes is the original array values, another set of nodes is the target values $1, 2, \dots, N$, and the costs are defined as above. Find a minimum-cost perfect matching in that graph to see which number each array item should be changed to, then sum up those costs to get your total number of moves required.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.