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$
1
  • $\begingroup$ To clarify: Would (1,2,1,2,1,2,…) count as “pairwise distinct”? $\endgroup$
    – gnasher729
    Feb 3 at 19:24

4 Answers 4

6
$\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, 2021 at 19:02
  • 3
    $\begingroup$ To help prove the algorithm is correct mathematically. $\endgroup$
    – John L.
    May 30, 2021 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$ May 30, 2021 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, 2021 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$
0
$\begingroup$

Why not doing like bellow- As you are given an array A of size N and elements are ranged between [1..N], and you need to make the Array non duplicate array element, so, the final array will be A=[1,2,...,N-1,N] We can have the total of this N*(N+1)/2 now given array can be like [N,N,....N](with length N) or [1,2,2,..N,N](with length N) or [1,1,...1](with length N). So we just need to make the array like A=[1,2,...,N-1,N]. We can just subtract the total count of given array which will give us the minimum number of moves.

        long total = (A.Length * (A.Length + 1)) / 2;
        long currentTotal = 0;
        for (int i = 0; i < A.Length; i++)
        {
            currentTotal += (long)A[i];
        }

        long minMove = Math.Abs(currentTotal - total);
$\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.