Make unique array with minimal sum

Question

It is a interview question. Given an array, e.g., [3,2,1,2,7], we want to make all elements in this array unique by incrementing duplicate elements and we require the sum of the refined array is minimal. For example the answer for [3,2,1,2,7] is [3,2,1,4,7] and its sum is 17. Any ideas?

Answer 1

It's not quite as simple as my earlier comment suggested, but it's not terrifically complicated.

First, sort the input array. If it matters to be able to recover the original order of the elements then record the permutation used for the sort.

Second, scan the sorted array from left to right (ie from low to high). If an element is less than or equal to the element to its left, set it to be one greater than that element.

Pseudocode

  sar = sort(input_array)
  for index = 2:size(sar)   ! I count from 1
      if sar(index)<=sar(index-1) sar(index) = sar(index-1)+1
  forend

Is the sum of the result minimal ? I've convinced myself that it is through some head-scratching and trials but I haven't got a formal proof.