Minimum unique array sum

Question

I got an interview question and my algorithm only pass given example test cases, and didn't pass all test cases.

Question: Given a sorted integer array, return sum of array so that each element is unique by adding some numbers to duplicate elements so that sum of unique elements is minimum.

I.e., if all elements in the array are unique, return the sum. If some elements are duplicates, then increment them to make sure all elements are unique so that the sum of these unique elements is minimum.

Some examples:

• input1[] = { 2, 3, 4, 5 } => return 19 = 2+3+4+5 (all elements are unique, so just add them up)
• input2[] = { 1, 2, 2 } => return 6 = 1+2+3 (index 2 is duplicate, so increment it)
• input3[] = { 2, 2, 4, 5 } => return 14 = 2+3+4+5 (index 1 is duplicate, so increment it)

These three are examples in the question, my simple algorithm is as follows and passed the given three examples, but didn't pass other cases where I couldn't see the inputs.

static int minUniqueSum(int[] A) {
    int n = A.length;


    int sum = A[0];
    int prev = A[0];

    for( int i = 1; i < n; i++ ) {
        int curr = A[i];

        if( prev == curr ) {
            curr = curr+1;
            sum += curr;
        }
        else {
            sum += curr;
        }
        prev = curr;
    }

    return sum;
}

I couldn't see other inputs which this algorithm failed. What I can think of other input examples are

{1, 1, 1, 1}  --> {1, 2, 3, 4}
{1, 1, 2, 2, 3, 3, 3} --> {1, 2, 3, 4, 5, 6, 7}

{1, 2, 4, 4, 7, 7, 8} --> I think this should be {1, 2, 3, 4, 6, 7, 8}  and my algorithm fails in this example because my algorithm has {1, 2, 4, 5, 7, 8, 9} whose sum is not minimum 

What are some other test cases and an algorithm which can pass all cases?

Some people are complaining that the question is not clear. I'd like to let you know about the problem. There was no clear description about the added number if it will be allowed only positive or positive and negative. Given three examples with input and output, and some others input and output cases which you are not allowed to see, write a program to pass all other unseen input / output cases as well. That was the question.

Answer 1

Your algorithm will fail in cases with more repeated values, for example

2, 2, 2

You'd get 7 instead of 9.

A minimal fix using your algorithm would be:

static int minUniqueSum(int[] A) {
    int n = A.length;

    int sum = A[0];
    int prev = A[0];

    for( int i = 1; i < n; i++ ) {
        int curr = A[i];

        if( prev >= curr ) {
            curr = prev+1;
        }
        sum += curr;
        prev = curr;
    }

    return sum;
}

*As pointed out in the comments, no need to sort an already sorted array.

Answer 2

In JavaScript

var list = [1, 1, 1, 10, 3, 2];

function minUniqueSum(arr) {
  const temp = arr.reduce((acc, cur) => {
    while (acc.includes(cur)) cur++;
    acc.push(cur);
    return acc;
  }, []);
  console.log(temp); // [1, 2, 3, 10, 4, 5]
  return temp.reduce((acc, cur) => acc + cur, 0);
}

var result = minUniqueSum(list);
console.log(result); // 25