# 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