Last Updated: 6 Jan, 2021
Find Duplicates In Array
Easy
Asked in companies
You are given an array/list 'ARR' consisting of N integers, which contains elements only in the range 0 to N - 1. Some of the elements may be repeated in 'ARR'. Your task is to find all such duplicate elements.
Note:
1. All the elements are in the range 0 to N - 1.
2. The elements may not be in sorted order.
3. You can return the duplicate elements in any order.
4. If there are no duplicates present then return an empty array.
Input Format:
The first line of the input contains an integer T, denoting the number of test cases.
The first line of each test case contains the integer N, denoting the size 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, every line of output contains K space-separated integers denoting the duplicate elements in the array.
Note
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10^2
1 <= N <= 10^4
0 <= ARR[i] <= N - 1
Time Limit: 1 sec
Approaches
- The most trivial approach would be to sort the array/list ‘ARR’ and then return the duplicates.
- After sorting the array in non-decreasing order, do the following for all the elements from i = 0 to i = n - 2:
- If ARR[i] == ARR[i + 1], then add ARR[i] to the the output list.
- While ARR[i] == ARR[i + 1], do i = i + 1, since we don’t want to add the same duplicate elements again and again.
- Else continue.
- After this loop, we will have all the duplicate elements from the array ‘ARR’ in our output array/list.
- There is another mathematical approach by which we can solve this problem in linear time and constant space.
- For every element ARR[i], increment the ARR[i]%N’th element by n i.e. ARR[ARR[i] % N] += N.
- Now again traverse the array and print the indices where ARR[i]/N is greater than 1. It guarantees that the number N has been added to that index.
- All these indices will be the repetitive elements because all the elements in the array are in the range 0 to N - 1 and ARR[i] will be greater than N if and only if ‘i’ has occurred more than once in the array.
Similar problems