Find Duplicates of array using bit array - GeeksforGeeks

Find Duplicates of array using bit array - GeeksforGeeks
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 ?.

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.

    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<arr.length; i++)

        {

            // Index in bit array

            int num  = arr[i] - 1;

 

            // If num is already present in bit array

            if (ba.get(num))

                System.out.print(num +" ");

 

            // Else insert num

            else

                ba.set(num);

        }

    }

Read full article from Find Duplicates of array using bit array - GeeksforGeeks