# Find Duplicates of array using bit array

You have an array of N numbers, where N is at most 32,000. The array may have duplicates entries and you do not know what N is. With only 4 Kilobytes of memory available, how would print all duplicates elements in the array ?.

Examples:

```Input : arr[] = {1, 5, 1, 10, 12, 10}
Output : 1 10
1 and 10 appear more than once in given
array.

Input : arr[] = {50, 40, 50}
Output : 50
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We have 4 Kilobytes of memory which means we can address up to 8 * 4 * 210 bits. Note that 32 * 210 bits is greater than 32000. We can create a bit with 32000 bits, where each bit represents one integer.

Note: If you need to create a bit with more than 32000 bits then you can create easily more and more than 32000;

Using this bit vector, we can then iterate through the array, flagging each element v by setting bit v to 1. When we come across a duplicate element, we print it.

Below is the implementation of the idea.

## Java

 `// Java program to print all Duplicates in array ` `import` `java.util.*; ` `import` `java.lang.*; ` `import` `java.io.*; ` ` `  `// A class to represent array of bits using ` `// array of integers ` `class` `BitArray ` `{ ` `    ``int``[] arr; ` ` `  `    ``// Constructor ` `    ``public` `BitArray(``int` `n) ` `    ``{ ` `        ``// Devide by 32. To store n bits, we need ` `        ``// n/32 + 1 integers (Assuming int is stored ` `        ``// using 32 bits) ` `        ``arr = ``new` `int``[(n>>``5``) + ``1``]; ` `    ``} ` ` `  `    ``// Get value of a bit at given position ` `    ``boolean` `get(``int` `pos) ` `    ``{ ` `        ``// Divide by 32 to find position of ` `        ``// integer. ` `        ``int` `index = (pos >> ``5``); ` ` `  `        ``// Now find bit number in arr[index] ` `        ``int` `bitNo  = (pos & ``0x1F``); ` ` `  `        ``// Find value of given bit number in ` `        ``// arr[index] ` `        ``return` `(arr[index] & (``1` `<< bitNo)) != ``0``; ` `    ``} ` ` `  `    ``// Sets a bit at given position ` `    ``void` `set(``int` `pos) ` `    ``{ ` `        ``// Find index of bit position ` `        ``int` `index = (pos >> ``5``); ` ` `  `        ``// Set bit number in arr[index] ` `        ``int` `bitNo = (pos & ``0x1F``); ` `        ``arr[index] |= (``1` `<< bitNo); ` `    ``} ` ` `  `    ``// Main function to print all Duplicates ` `    ``static` `void` `checkDuplicates(``int``[] arr) ` `    ``{ ` `        ``// create a bit with 32000 bits ` `        ``BitArray ba = ``new` `BitArray(``320000``); ` ` `  `        ``// Traverse array elements ` `        ``for` `(``int` `i=``0``; i

## C#

 `// C# program to print all Duplicates in array ` `  `  `// A class to represent array of bits using  ` `// array of integers  ` `using` `System; ` ` `  `class` `BitArray  ` `{  ` `    ``int``[] arr;  ` ` `  `    ``// Constructor  ` `    ``public` `BitArray(``int` `n)  ` `    ``{  ` `        ``// Devide by 32. To store n bits, we need  ` `        ``// n/32 + 1 integers (Assuming int is stored  ` `        ``// using 32 bits)  ` `        ``arr = ``new` `int``[(``int``)(n >> 5) + 1];  ` `    ``}  ` ` `  `    ``// Get value of a bit at given position  ` `    ``bool` `get``(``int` `pos)  ` `    ``{  ` `        ``// Divide by 32 to find position of  ` `        ``// integer.  ` `        ``int` `index = (pos >> 5);  ` ` `  `        ``// Now find bit number in arr[index]  ` `        ``int` `bitNo = (pos & 0x1F);  ` ` `  `        ``// Find value of given bit number in  ` `        ``// arr[index]  ` `        ``return` `(arr[index] & (1 << bitNo)) != 0;  ` `    ``}  ` ` `  `    ``// Sets a bit at given position  ` `    ``void` `set``(``int` `pos)  ` `    ``{  ` `        ``// Find index of bit position  ` `        ``int` `index = (pos >> 5);  ` ` `  `        ``// Set bit number in arr[index]  ` `        ``int` `bitNo = (pos & 0x1F);  ` `        ``arr[index] |= (1 << bitNo);  ` `    ``}  ` ` `  `    ``// Main function to print all Duplicates  ` `    ``static` `void` `checkDuplicates(``int``[] arr)  ` `    ``{  ` `        ``// create a bit with 32000 bits  ` `        ``BitArray ba = ``new` `BitArray(320000);  ` ` `  `        ``// Traverse array elements  ` `        ``for` `(``int` `i = 0; i < arr.Length; i++)  ` `        ``{  ` `            ``// Index in bit array  ` `            ``int` `num = arr[i];  ` ` `  `            ``// If num is already present in bit array  ` `            ``if` `(ba.``get``(num))  ` `                ``Console.Write(num + ``" "``);  ` ` `  `            ``// Else insert num  ` `            ``else` `                ``ba.``set``(num);  ` `        ``}  ` `    ``}  ` ` `  `    ``// Driver code  ` `    ``public` `static` `void` `Main() ` `    ``{  ` `        ``int``[] arr = {1, 5, 1, 10, 12, 10};  ` `        ``checkDuplicates(arr);  ` `    ``}  ` `}  ` ` `  `// This code is contributed by Rajput-Ji `

Output:

```1 10
```

## tags:

Arrays Bit Magic Arrays Bit Magic