Tutorialspoint.dev

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

Asked In: Amazon



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<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);
        }
    }
  
    // Driver code
    public static void main(String[] args) throws
                              java.lang.Exception
    {
        int[] arr = {1, 5, 1, 10, 12, 10};
        checkDuplicates(arr);
    }
}

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 

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter