# Minimum number of increment / decrement operations to make an array distinct?

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.

## 3 Answers

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|.$$

• What's the goal of the exercise ?? May 30 '21 at 19:02
• To help prove the algorithm is correct mathematically. May 30 '21 at 20:48

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

$$$$\sum_{i=1}^{N-1} i$$$$

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.

• 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. May 30 '21 at 16:21
• @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. May 30 '21 at 16:30

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.