Problem

Submissions

Hints & solutions

Discuss

Find Duplicates Using Bit Array

Moderate

0/80

Average time to solve is 10m

Contributed by

7 upvotes

Asked in companies

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]

Detailed explanation ( Input/output format, Notes, Images )

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

Sample input 1:

2
5
4 3 4 2 1
6
1 1 8 6 5 5

Sample output 1:

4 
1 5

Explanation For Sample input 1:

For the first test case :
There is only one element with duplicate entries, that is 4 on indexes 1 and 3. 

For the second test case :
There are two elements with duplicate entries
Element 1 exists on indexes 0 and 1.
Element 5 exists on indexes 4 and 5.

Sample input 2:

2
5
7 7 4 3 4
6
1 2 3 4 5 7

Sample output 2:

4 7

Hint 1

Hint 2

Can you think of a brute force approach?

Approaches (2)

Approach 1

Approach 2

Brute Force

The idea is very simple. For each element, we will iterate over the whole ‘ARR’ to check whether duplicate exits or not.

Initialize an output array/list of integers say ‘ANS’ which will store duplicates.
Iterate over the ‘ARR’ for 0 <= i < ‘N’ and do :
- Iterate over the ‘ARR’ for i+1 <= j < ‘N’ and do:
  - If ‘ARR[i]’ is equal to ‘ARR[j]’ :
    - Append ‘ARR[i]’ into ‘ANS’
Return ‘ANS’.

Time Complexity

O(N ^ 2), where N is the length of the given array/list ‘ARR’.

As we are running two nested loops over an array/list of length N.

Space Complexity

O(1)

As we are using constant extra memory.

(100% EXP penalty)

Find Duplicates Using Bit Array

Console