17

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.

5
  • In your last test-case, you are removing 1 from the 2nd index. However, in your question you say that you can only made it unique by "adding minimum numbers if duplicates".
    – MathBunny
    Jul 14, 2016 at 21:31
  • How should {1, 2, 4, 4, 7, 7, 8} become {1, 2, 3, 4, 6, 7, 8} if you are only allowed to add to numbers?
    – tobias_k
    Jul 14, 2016 at 21:31
  • So you are allowed to add negative numbers as long as the array stays sorted?
    – stark
    Aug 17, 2016 at 11:40
  • One test case might be an int which is at the max range of Integer. Causing a overflow. You might need to upcast to long before incrementing to avoid that. Your sum will probably also need to be a big int or double. Jun 13, 2019 at 10:02
  • The task does not state explicitly that the array shall be ordered subsequent to adding natural numbers so the elements are unique.
    – greybeard
    Dec 6, 2023 at 18:01

16 Answers 16

11

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.

1
  • @kremzeek your example isn't sorted
    – Amit
    Jul 7, 2020 at 6:37
3

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
2

I did like this, without sort.

    // Complete the getMinimumUniqueSum function below.
static int getMinimumUniqueSum(int[] arr) {

 int sum = 0;

 ArrayList < Integer > arrayList = new ArrayList < Integer > (arr.length);

 arrayList.add(arr[0]);


 for (int i = 1; i < arr.length; i++) {

  int val = arr[i];

  while (arrayList.contains(val)) {

   val++;
  }

  arrayList.add(val);

 }



 for (int i = 0; i < arrayList.size(); i++) {
  sum += arrayList.get(i);
 }

 return sum;
}

And it passed all (13) test cases.

1
  • Given a sorted integer array, you don't need to sort and using Collection.contains() is overkill. Arraylist.contains() is harmful to performance.
    – greybeard
    Aug 2, 2019 at 6:22
1

While this solution is based on java the thought process can be applied everywhere.

Your solution is nearly correct and optimized. Using multiple for loops will slow things down A LOT and thus should be avoided if possible! Since your array is already pre-sorted you have enough with 1 for loop.

Your assumption that you had the last test case wrong does not seem to be correct since increment means you can only do +1 (and indeed most questions limit this assignment to increments only.)

What you missed was the max range of the Integers.

If they pass a Integer.MAX_VALUE, your sum will overflow and be negative instead. So your sum variable needs to be of a bigger type. double or BigInteger should work (BigInteger would be best).

Also when they pass MAX_VALUE twice your curr+1 will also overflow becoming negative instead. So you want your curr and prev to also be a larger type. long should do for this.

 public static double calculateMinSumSorted(int[] input){
    double sum = input[0];

    long prev = input[0];
    long cur;

    for(int i = 1 ; i < input.length ; i++){
        cur = input[i];
        if(cur <= prev){
            cur = ++prev;
        }
        prev = cur;
        sum += cur;
    }
    return sum;
}

Here is some of the test cases I used:

@Test
public void testSimpleArray(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,2,3,4});
    Assert.assertEquals(10, test1, 0.1);

}
@Test
public void testBeginningSameValues(){
    double test1 = muas.calculateMinSumSorted(new int[]{2,2,3,4});
    Assert.assertEquals(14, test1, 0.1);
}
@Test
public void testEndingSameValues(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,2,4,4});
    Assert.assertEquals(12, test1, 0.1);
}
@Test
public void testAllSameValues(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,1,1,1});
    Assert.assertEquals(10, test1, 0.1);
}

@Test
public void testOverMaxIntResult(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,2,3,3,4,4,4,4,4,Integer.MAX_VALUE});
    System.out.println(test1);
    Assert.assertEquals(2147483692.0, test1, 0.1);
}

@Test
public void testDoubleMaxIntArray(){
    double test1 = muas.calculateMinSumSorted(new int[]{2,2,3,4,5,6,7,8,9, Integer.MAX_VALUE, Integer.MAX_VALUE});
    Assert.assertEquals(4294967349.0, test1, 0.1);
}

@Test
public void testDoubleMinIntArray(){
    double test1 = muas.calculateMinSumSorted(new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE,2,2,3,4,5,6,7,8,9});
    Assert.assertEquals(-4294967241.0, test1, 0.1);
}
1
1

In C++:

int64_t getMinimumUniqueSum(std::vector<int> arr)
{
    std::sort(arr.begin(), arr.end());

    int64_t sum = arr[0];
    size_t i = 0;
    size_t j = 1;
    size_t gap_i = j;
    int avail_val = arr[j] + 1;

    while (j < arr.size()) {
        // find next gap with available values
        if (j > gap_i) {
            gap_i = j;
            avail_val = arr[gap_i] + 1;
        }
        while (gap_i < arr.size() && arr[gap_i] <= avail_val) {
            avail_val = arr[gap_i] + 1;
            gap_i++;
        }

        if (arr[i] == arr[j]) {
            // update duplicated value
            arr[j] = avail_val;
            avail_val++;
        } else {
            // move index of prev value - i
            i = j;
        }

        sum += arr[j];
        j++;
    }

    return sum;
}

Straightforward solution that uses hash set would be mush slower:

int64_t getMinimumUniqueSum_Slow(std::vector<int> arr)
{
    std::unordered_set<int> s;

    int64_t sum = 0;

    for (int a : arr) {
        while (s.find(a) != s.end()) {
            a++;
        }
        s.insert(a);
        sum += a;
    }

    return sum;
}

Slow version takes about 10s to process array with 10^5 numbers.

While optimized one takes about 0.5s to process array with 10^7 numbers.

But while the slow solution is obviously correct - we can use it for testing of the optimized one:

std::vector<int> random_vec(size_t size, int min_val, int max_val)
{
    std::random_device rnd_device;
    std::mt19937 mersenne_engine {rnd_device()};
    std::uniform_int_distribution<int> dist {min_val, max_val};

    auto gen = [&dist, &mersenne_engine](){
                   return dist(mersenne_engine);
               };

    std::vector<int> arr(size);
    generate(begin(arr), end(arr), gen);

    return arr;
}

int main()
{
    for (int i = 0; i < 1000; i++) {
        printf("%d\n", i);
        auto arr = random_vec(i*10+1, -5, 5);

        int64_t x = getMinimumUniqueSum(arr);
        int64_t y = getMinimumUniqueSum_Slow(arr);
        if (x != y) {
            printf("Results not match: fast -> %lld, slow -> %lld !!!\n\n", x, y);
            return 1;
        }
    }

    return 0;
}

1
// 1,1,2,3 -> 1,2,2,3 -> 1,2,3,3 -> 1,2,3,4 => 10
// 2,2,2 -> 2,3,2 -> 2,3,3 -> 2,3,4 => 9
public int calculateMinSumSorted(int[] input) {
    int sum = input[0];
    for (int i = 1, v = sum; i < input.length; v = input[i++]) {
        if (input[i] <= input[i - 1]) {
            input[i--] = ++v;
        } else {
            sum += input[i];
        }
    }
    return sum;
}
0

It you're allowed to add negative values to any of the inputs then the minimum is just the Nth triangular number where N is the number of elements in the array. (I'm presuming that we're dealing only with positive numbers for the adjusted array since we could make it arbitrarily small (negative) otherwise.

So you're algorithm is just a matter of looking for a pair of consecutive values that are the same. If not found return the sum else N * (N + 1) / 2.


If instead it's true that only duplicate elements can be adjusted, then the approach is to find holes between consecutive elements and fill them up with previously "queued" values. The actual values of the "queued" elements is irrelevant and only a counter is necessary. Below is a C# solution where I'm assuming that the adjustments to elements must be positive values. So that means we can't go backward and fill unused holes which simplifies the problem.

int F()
{
    int[] a = {2, 2, 2, 3, 8, 9}; // sorted list

    int n = 0; /* num */   int p = 0; /* prev; zero is an invalid value in the list */
    int q = 0; /* queue */ int s = 0; /* sum */

    for (int i = 1; i < a.Length; i++)
    {
        n = a[i];
        if (n == p)
            q++; // increment queue on duplicate number
        else
        {
            // for every hole between array values, decrement queue and add to the sum
            for (int j = 1; q > 0 && j < n - p; j++, q--)
                s += p + j;
            s += (p = n);
        }
    }
    // flush the queue
    for (; q > 0; q--)
        s += ++n;

    return s;
}

You example {1, 2, 4, 4, 7, 7, 8} suggests that the previous assumption is not valid. So I went ahead and wrote a version that uses a queue to store skipped holes for later filling. It's not really that painful, and it's very similar in structure, but it might still be too much for most interviews.

using System.Collections.Generic;
int F2()
{
    int[] a = {1, 1, 8, 8, 8, 8, 8}; // sorted list

    int n = 0; /* num */   int p = 0; // prev; zero is an invalid value in the list
    int q = 0; /* queue */ int s = 0; // sum
    Queue<int> h = new Queue<int>(); // holes

    for (int i = 1; i < a.Length; i++)
    {
        n = a[i];
        if (n == p)
            q++; // increment queue on duplicate number
        else
        {
            for (int j = 1; j < n - p; j++)
                if (h.Count <= q + a.Length - i) // optimization
                    h.Enqueue(p + j);
            s += (p = n);
        }
    }
    // flush the queue
    for (; q > 0; q--)
        s += h.Count > 0 ? h.Dequeue() : ++n;

    return s;
}

Try them both out here: http://rextester.com/APO79723

7
  • You are right, the question doesn't specify what a 'number' is, so we can e.g. assume it to be negative (what you did) and just add e.g. the IEEE 754 'negative infinity' or the smallest real double or - if restricted to positive values - add the difference to the next smallest float etc. Your answer however is flawed in that if there were e.g. only one repeated number [1,5,5,9] you can only modify one of the 5 elements which won't allow the other 'holes' to be filled and the sum can't possibly be N * (N + 1) / 2.
    – le_m
    Jul 14, 2016 at 22:52
  • @le_m The question doesn't specify which values were permissible for modification. "add some numbers" is a little unclear and I did indeed state this assumption in my answer
    – shawnt00
    Jul 14, 2016 at 23:14
  • IMHO the question is precise here: "by adding some numbers to duplicate elements" - well, one could argue that only one or both duplicate elements can be modified, but still, we couldn't guarantee your above assumption about the min. sum.
    – le_m
    Jul 14, 2016 at 23:22
  • @le_m You are right. I was focusing on the restatement just beneath that. But as noted I was not confident about it and I stated my assumption.
    – shawnt00
    Jul 14, 2016 at 23:29
  • Right, the whole question is not very clear and begs to be taken apart - probably not the best course of action during an interview, but who would want to work for an employer who can't even get the questions right? :)
    – le_m
    Jul 14, 2016 at 23:40
0
int a[] = {1,2,2,3,5,6,6,6,6 }; So what would be elements in array for sum
As per above problem statement it would be {1,2,3,4,5,6,7,8,9 }

Solution
public static void uniqueSum(){
        int a[] = {1,2,2,3,5,6,6,6,6 };
        int n = a.length;
        int sum = a[0];
        int prv=a[0];
        for(int i=1; i<n;i++){
            int cur = a[i];
            if(cur==prv){
                cur = cur+1;
                sum+= cur;
                System.out.print("--"+cur);
            }else{
                if(cur<prv){
                    cur = prv +1;
                }
                sum += cur;
            }
            prv = cur;
        }
        System.out.println("===================== "+sum);
    }
0

You can try the below code.

int a[] = {1, 1 , 1};
ArrayList<Integer> arr = new ArrayList<Integer>();
HashMap hash = new HashMap();
for(int i=0;i<a.length;i++){
    arr.add(a[i]);
}
int sum = 0;
hash.put(0, arr.get(0));
sum = (int) hash.get(0);
for(int i=1;i<arr.size();i++){
    for(int j=1;j<=a.length;j++){
        if(hash.containsValue((arr.get(i)))){
            arr.set(i, arr.get(i)+1);
        }else{
            hash.put(i, arr.get(i));
            sum += (int) hash.get(i);
            break;
        }
    }
}

System.out.println(sum);

PS: Even I got this question in my interview, the above code passed all the test cases.

2
  • Mind explaining your rationale along with your code?
    – Sameen
    Feb 17, 2017 at 23:48
  • What is the result to be expected for { 0 }, what does this code produce and why?
    – greybeard
    Aug 3, 2019 at 4:48
0

public static int minSum(int arr[]){

    for(int i=0; i<arr.length-1;i++){

        if(arr[i]==arr[i+1]){

            arr[i+1]= arr[i+1]+1;
        }
    }

    int sum=0;

    for(int i=0; i<arr.length;i++){

        sum=sum+arr[i];
    }

    System.out.println("sum: "+sum);
    return sum;
}
0
0

Going by your description of hidden I/O, it's probably a HackerRank Test question. A better way to state the problem is "Given a sorted array of numbers, make the numbers distinct by incrementing them (num++ at a time) in such a way that the array sum is minimized."

The problem allows only increments i.e. increase a number by 1 at a time. This also ensures that the array always remains sorted. so {1, 2, 4, 4, 7, 7, 8} --> {1, 2, 4, 5, 7, 8, 9}

Here is the problem with the solution. https://www.geeksforgeeks.org/making-elements-distinct-sorted-array-minimum-increments/

0

Working solution (JAVA 7) :

public static int getMinimumUniqueSum(List <Integer> arr){
    int sum = 0, val = 0;
    ArrayList < Integer > arrayList = new ArrayList < Integer > (arr.size());
    arrayList.add(arr.get(0));
    for (int i = 1; i < arr.size(); i++) {
        val = arr.get(i);
        while (arrayList.contains(val)) {
            val++;
        }
        arrayList.add(val);    
    }
    for (int i = 0; i < arrayList.size(); i++) {
        sum += arrayList.get(i);
    }
    return sum;
}
0
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

/* No sorting required. Works even with random list */
public static int getMinUniqueSum(List<Integer> list)
    {
        Set<Integer> set = new HashSet<Integer>();

        int sum = 0;

        for (Integer val : list) 
        {
            if(!set.add(val))
            {
                while(true)
                {
                    Integer temp = val + 1;
                    if(set.add(temp))
                    {
                        sum = sum + temp;
                        break;
                    }
                }
            }
            else
            {
                sum = sum + val;
            }
        }

        return sum;
    }

    public static void main(String[] args) 
    {
        Scanner s = new Scanner(System.in);

        System.out.println("Enter size of the list");

        int n = s.nextInt();

        List<Integer> list = new ArrayList<Integer>(n);

        System.out.println("Enter " + n + " elements of the list");

        for(int i = 0; i < n; i++)
            list.add(s.nextInt());

        s.close();

        System.out.println("MinUniqueSum = " + getMinUniqueSum(list));

    }
}
1
  • Given a sorted integer array, no sorting is required, anyway.
    – greybeard
    Aug 2, 2019 at 6:26
0

In Haskell:

countdups _ _  [] = []
countdups first prev (x:xs)             
        | (prev >= x) && (first /= True) = (prev+1) : countdups False (prev+1)  xs 
        | otherwise = x: countdups False x xs

minsum list =  sum $ countdups True 0 (sort list)

Here is some of the test cases I used:

countdups True 0 [2, 3, 4, 5]

[2,3,4,5]

minsum = 14 

countdups True 0 [1, 2, 2]

[1,2,3]

minsum = 6

countdups True 0 [2, 2, 4, 5]

[2,3,4,5]

minsum = 14

countdups True 0 [1,2,2,3,7]

[1,2,3,4,7]

minsum = 17

countdups True 0 [1,1,1,2,3,10]

[1,2,3,4,5,10]

minsum = 25

countdups True 0 [1,1,1,1]

[1,2,3,4]    

minsum= 10

countdups True 0 [1,2,3,3,4,4,4,4,4,2147483647]

[1,2,3,4,5,6,7,8,9,2147483647]

minsum= 2147483692
0

let arr = [1,2,4,4,7,7,8]

//make duplicates null

function x(arr){
for(let i=0; i<arr.length-1; i++){
  if(arr[i]==arr[i+1])arr[i]=0;
}
console.log(arr.sort());
let i=0;
while(arr[i]==0)i++;

console.log(i);
let ans =[];


for(let k=i; k<arr.length; k++){
  if(arr[k+1]>arr[k]+1){
      let n = arr[k+1]-arr[k];
      for(let l=0; l<n-1;l++){
        ans.push(arr[k]+l+1)
        if(ans.length == i) return ans;
      }
  }
}

} 

arr.sort();
let nums = x(arr);
for(let i =0; i<arr.length; i++){
  if(i<nums.length)arr[i] += nums[i];
}
arr.sort();
console.log(arr);

2
  • Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
    – Community Bot
    Dec 12, 2023 at 20:13
  • A wall of code usually makes a bad answer and is likely to be removed, if you provide no explanation of your code and your solution.
    – Miguel
    Dec 13, 2023 at 12:25
-1

Using Collections in java helps a lot , Here i use HashMap as it stores values for every Unique Key

My Key in hashmap is the array elements and the value is the no. of counts as it appears in the array.

package uniquesum;
import java.util.*;
public class Uniquesum {
static HashMap<Integer, Integer> hp = new HashMap<Integer, Integer>();
    static int Sum(int arr[]){
        int sum=0;
        Arrays.sort(arr);
        hp.put(arr[0], 1);
        for(int i=1; i<arr.length; i++){
            if(hp.containsKey(arr[i])){

                Integer val = hp.get(arr[i]);
                hp.put(arr[i], val+1);
                hp.put(arr[i]+val, 1);                
            }
            else{
                hp.put(arr[i], 1);
            }
        }

        for(Map.Entry m:hp.entrySet()){
            sum = sum + (int)m.getKey();
        }
        return sum;
    }
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int arr[] = new int [n];
        for(int i=0; i<n;i++){

        arr[i] = scan.nextInt();
        }

        System.out.println("Sum is " + Sum(arr));


    }

}
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.