Sort the array. Scan left to right. Each element must be at least one more than the previous.
If , increment to . The cost is the difference.
Here's greedy because you fix each violation with the minimum possible increment.
You cannot do better: the element must be unique and at least as large as it was. Why this is optimal: each element must be at least its original value.
If , the smallest valid value is . Choosing anything larger would waste increments. The greedy choice minimizes cost at each step.