Last Updated: 1 Dec, 2020
Make Unique Array
Easy
Asked in companies
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.
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.
Approaches
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.
The idea is to sort the array and then check if the consecutive elements are the same. If they are, then we increase the counter to remove elements.
The steps are as follows:
- Maintain a variable ‘minRemoves,’ which denotes the minimum number of elements we have to remove.
- Sort the array in ascending order.
- Maintain a variable ‘prev’ which tells us what the previous element that we encountered was.
- Loop from i = 0 to i = ‘N’ - 1.
- If the current element, i.e., ‘arr’[‘i’], is equal to the ‘prev’, then increase ‘minRemoves’ by 1.
- Else change ‘prev’ to ‘arr’[‘i’].
- Return ‘minRemoves’ as the final result.
The idea is to use a hash map, which stores all the elements we have seen so far, and if any element re-appears, then we remove it. Else we mark that element as present.
The steps are as follows:
- Maintain a variable ‘minRemoves’, which denotes the minimum number of elements we have to remove.
- Maintain a Hash-Map ‘present to mark all the elements that are present.
- Loop from 0 to ‘N’ - 1 to traverse ‘arr’:
- If ‘arr[i]’ is already present in the hashmap, then increase ‘minRemoves’ by 1.
- Else mark ‘arr[i]’ as present.
- Return ‘minRemoves’ as the final result.