Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 25 Feb, 2021

Moderate

```
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.
```

```
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]
```

```
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.
```

```
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.
```

```
You don’t have to print anything, it has already been taken care of. Just implement the given function.
```

```
1<= T <=100
1 <= N <= 32000
0 <= ‘ARR[i]’ <= 32000
Time limit: 1 second
```

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’

- If ‘ARR[i]’ is equal to ‘ARR[j]’ :

- Iterate over the ‘ARR’ for i+1 <= j < ‘N’ and do:
- Return ‘ANS’.

The idea is to use a bit array as we can have a maximum of 32000 elements but with given memory constraints 4KB which will evaluate to 32778 bits ( 4*8*1024 ), we can address up to 32778 addresses.

So we will make a Bits array for the purpose of hashing. Actually, an integer has a size of 4 Byte or we can say 32 Bits. So we will make an integer array/list say ‘BIT_ARRAY’ of size 1000 and each ‘BIT_ARRAY’ index will be used to address 32 elements so now we can address up to 32000 elements with help of ‘BIT_ARRAY’.

- Initialize an array/list of integers ‘BIT_ARRAY’ of size 1000 with 0.
- Initialize an output array/list of integers ‘ANS’ which will store duplicates.
- Iterate over the ‘ARR’ for 0 <= i < ‘N’ and do :
- Find the index of ‘BIT_ARRAY’ which has the address for ‘ARR[i]’ as :
- The index will be equal to ‘ARR[i]’ divided by 32.

- Find the bit of index (BIT_NO) which have the address for ‘ARR[i]’ as :
- Taking AND operation of ‘ARR[i]’ with 31(as each element has 32 Bits).

- Let ‘VAL’ = ‘BIT_ARRAY[ 2^BIT_NO]’ .
- If ‘VAL’ is equal to 1 :
- It means the current element is duplicate so append ‘ARR[i]’ in ‘ANS’.

- If ‘VAL’ is equal to 1 :
- Set ‘BIT_ARRAY[ 2^BIT_NO]’ = 1.

- Find the index of ‘BIT_ARRAY’ which has the address for ‘ARR[i]’ as :
- Return ‘ANS’.

Similar problems

Search In A Sorted 2D Matrix

Moderate

Posted: 23 Nov, 2022

Ninja And The Strictly Increasing Array

Moderate

Posted: 27 Nov, 2022

Negative To The End

Easy

Posted: 16 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023