 New update is available. Click here to update.

# Find Duplicates Using Bit Array

Last Updated: 25 Feb, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### You are given an array/list ‘ARR’ of N elements where N <= 32000. ‘ARR’ can have duplicate entries. Your task is to find duplicate elements, provided you can use a maximum of 4 KiloBytes of extra memory.

##### Note :
``````Any element can have a maximum of two entries, or we can say a duplicate element will have two entries.

You need to return an array/list of duplicate elements where the elements in the array/list will be in increasing order.
``````
##### For example:
``````Given ‘ARR’  = [1, 3, 2, 7, 4, 2, 1]

In this ‘ARR’, 1 and 2 have duplicate entries.

So, the output array/list = [1, 2]
``````
##### Input Format:
``````The first line of input contains a single integer T, representing the number of test cases.
Then the T test cases follow.

The first line of each test case contains a number N denoting the size of the array/list ‘ARR’.

The second line contains N space-separated distinct integers representing the ‘ARR’ elements.
``````
##### Output format:
``````For each test case print the output array/list where elements are separated by a single space.

The output of every test case will be printed in a separate line.
``````
##### Note :
``````You don’t have to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints
``````1<= T <=100
1 <= N <= 32000
0 <= ‘ARR[i]’ <= 32000

Time limit: 1 second
``````