Problem 9: Unique Elements

Software Development
#1

Problem 9: Unique Elements

Problem Description

You are given an array A of N elements. You have to make all elements unique, to do so in one step you can increase any number by one.

Find the minimum number of steps.

Problem Constraints

1 <= N <= 105
1 <= A[i] <= 109

Input Format

The only argument given is an Array A, having N integers.

Output Format

Return the Minimum number of steps required to make all elements unique.

Example Input

Input 1:

A = [1, 1, 3]

Input 2:

A = [2, 4, 5]

Example Output

Output 1:

1

Output 2:

0

Example Explanation

Explanation 1:

We can increase the value of 1st element by 1 in 1 step and will get all unique elements. i.e [2, 1, 3].

Explanation 2:

All elements are distinct.

Note: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt?

  1. All submissions are automatically checked for plagiarism, and flagged solutions might not be counted towards the total score.
  2. Do not hesitate to discuss the solution with your batchmates, or take help from your Coach to build intuition.
  3. DO NOT move on from a problem until you have understood the approach very well.
  4. Plagiarism would defeat the purpose of learning a new pattern and concept.
#2
  1. All submissions are automatically checked for plagiarism, and flagged solutions might not be counted towards the total score.
  2. Do not hesitate to discuss the solution with your batchmates, or take help from your Coach to build intuition.
  3. DO NOT move on from a problem until you have understood the approach very well.
  4. Plagiarism would defeat the purpose of learning a new pattern and concept.

Solution: Unique Elements in Java

import java.util.*;
public class Solution {
    public int solve(ArrayList<Integer> A) {
        // [1, 2, 1, 3, 3]
        int count = 0;
        if (A.size() == 1) return 0; // Covering the corner or edge case where there is only one element in the ArrayList
        Collections.sort(A); // This will take average of O(NLogN) time, where N is the number of elements in the ArrayList
        for (int i = 1; i < A.size(); ++i ) {
            if ( A.get(i-1) >= A.get(i) ) {
                count += A.get(i-1) + 1 - A.get(i);
                A.set( i, A.get(i-1) + 1 );
            }
        }
        return count;
    }
}