Make Unique Array

Easy
0/40
Average time to solve is 10m
profile
Contributed by
26 upvotes
Asked in companies
CodenationNagarro Software

Problem statement

You are given an array ‘ARR’ of size ‘N,’ and you have to tell the minimum number of elements that need to be removed such that the array contains all distinct elements. More formally, there should not be any ‘I’ and ‘J’ such that ‘I’ != ‘J’ and ‘ARR’[‘I’] = ‘ARR’[‘J’].

For example:

Given ‘N’ = 4, 
'ARR' = { 1, 2, 1, 2} 
Then the answer is 2 because 1 and 2 are repeated once therefore we need to remove 2 elements.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer, ‘N,’ where ‘N’ is the number of elements of the array.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.
Output Format : 
For each test case, You are supposed to return an integer denoting the minimum number of elements to remove from the array, such that the array contains all distinct elements.
Note: 
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints: 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 5000
0 <= 'ARR[i]’ <= 10 ^ 6

Time Limit: 1 sec.

Sample Input 1 :

2
4
1 2 1 2
5
3 6 7 12 13

Sample Output 1 :

2
0

Explanation of the Sample Input 1:

In the first test case, there are 4 elements in the array and elements at index 2 and 3(0-based indexing) are repeated. Therefore we need to remove 2 elements to make this array of all distinct elements.

In the second test case, there are 5 elements in the array and all the elements are unique therefore we don't need to remove any element from the array.

Sample Input 2 :

2
4
1 1 1 1
5
1 2 3 1 2

Sample Output 2 :

3
2
Hint

Can we check for each element?

Approaches (3)
Brute force

The idea is to maintain an array which contains only unique elements, then for each element in the given array search whether the unique array has that element or not. In the return ‘N’ minus the size of the unique array.

The steps are as follows:

  • Maintain an array ‘uniqueArray’ which contains only unique elements.
  • Declare function ‘findElement’:
    • Which takes the ‘uniqueArray’ and ‘val’ to find as parameters.
    • It searches for the ‘val’ in ‘uniqueArray’ and returns true if found else false.
  • For every element in the array check if it is present in the ‘uniqueArray’ if not then add in the ‘uniqueArray’
  • Return ‘N’ - size of ‘uniqueArray’ as the final result.
Time Complexity

O(N ^ 2), where ‘N’ is the number given.

 

Since in the worst case we are traversing the whole array for each element, the final time Complexity will be O(N ^ 2). 

Space Complexity

O(N).
 

Since we are using an array to store elements hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Make Unique Array
Full screen
Console