Minimum Unique Array Amount

Question

I had a question with an interview, and my algorithm passes only approximate test cases and did not pass all test cases.

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

Ie, if all the elements in the array are unique, return the sum. If some elements are duplicated, then increase them to make sure that all elements are unique, so that the sum of these unique elements is minimal.

Some examples:

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

These three examples in this question, my simple algorithm is the following and passed these three examples, but did not go through other cases where I could not 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 could not see other inputs that this algorithm failed. I can think of other input examples:

 {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 that can convey all cases?

Some people complain that the question is not clear. I would like to inform you about the problem. There was no clear description of the added number if it would be allowed only positive or positive and negative. Considering three examples of input and output, as well as some other cases of input and output that you cannot see, write a program to transfer all other invisible cases of input-output. It was a question.

Answer 1

Your algorithm will fail in cases with more duplicate values, e.g.

2, 2, 2

You will get 7 instead of 9.

The 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 indicated in the comments, there is no need to sort an already sorted array.

Answer 2

I liked it so much, without sorting.

  // 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 went through all (13) test cases.

Answer 3

Although this solution is based on Java, the thought process can be applied everywhere.

Your decision is almost correct and optimized. Using multiple for loops will slow down the LOT, and should be avoided whenever possible! Since your array is already pre-sorted, a 1 for loop is enough for you.

Your assumption that you made a mistake in the last test case seems to be wrong, since an increment means that you can only do +1 (and indeed, most questions limit this assignment to only increments).

What you missed was the maximum range of integers.

If they pass Integer.MAX_VALUE, your amount will be overflowed and will be negative. Therefore, your sum variable should be of a larger type. double or BigInteger should work (BigInteger would be better).

Also, when they pass MAX_VALUE twice, your +1 course will also be full and become negative. So you want your curr and prev to be of a larger type too. it takes a long time to do 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 are 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); } 

Answer 4

You are 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 assume that we are dealing only with positive numbers for the corrected array, since we could make it arbitrarily small (negative) otherwise.

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

---

If instead it is true that only repeating elements can be adjusted, then the approach is to search for holes between consecutive elements and fill them with previously “queued” values. The actual values ​​of the “queued” items are irrelevant, and only a counter is needed. The following is a C # solution where I assume that adjustments to the elements should be positive. This means that we cannot go back and fill in unused holes, which will simplify 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; } 

---

Example {1, 2, 4, 4, 7, 7, 8} assumes that the previous assumption is false. So I went ahead and wrote a version that uses a queue to store missing holes for later filling. It doesn't really hurt, and it looks a lot like structure, but it could 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 both of them: http://rextester.com/APO79723

Answer 5

 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); } 

Answer 6

You can try the code below.

 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 code above passed all the test cases.

Answer 7

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; } 

Answer 8

Judging by the description of hidden I / O, this is probably a matter of the HackerRank test. The best way to state the problem is: "Given a sorted array of numbers, select the numbers by increasing them (num ++ at a time) so that the sum of the array is minimized."

The problem allows only an increase, that is, an increase in the 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/

Answer 9

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; } 

Answer 10

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 

Answer 11

 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)); } } 

Answer 12

Using collections in Java helps a lot, here I use a HashMap as it stores values ​​for each unique key

My key in hashmap is the elements of the array, but the value is not. samples 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)); } } 

Answer 13

I tried this in C # and it seems correct according to the test cases I tried.

 static int getMinimumUniqueSum(int[] s) { List<int> sa = new List<int>(s); sa.Sort(); for (int i = 1; i < sa.Count(); i++) { if (sa.ElementAt(i) == sa.ElementAt(i - 1)) { int p = sa.ElementAt(i); sa.RemoveAt(i); sa.Insert(i, p + 1); sa.Sort(); i--; } } return sa.Sum(); }