[11.4] Find duplicate in N = 32,000

1. Example

Bit Vector STORE number into corresponding position
Multiple int
int[] array => array[0]     ,array[1], .......
                        32 bit       32 bit
int wordNumber = numberPos >> 5;                           ==> array Index

int bitNumber = (numberPos & 0x1F); // mod by 32  ==> array element int bit
// NOTE: divide by 32 is because each int is 32 bit
// divide by 8 is because each byte is 8 bit1~ N = 1 ~ 32000 = 32 *1000 = 2^4 * 2^10 = 2 ^14
4KB = 4*2^10*8 btis = 2 ^ 15 bits
2 ^ 15 > 2 ^14
each bit represents a integer


2. Implementation

public static void checkDuplicates(int[] array)
{


     BitSet bs = new BitSet(32000);
     for (int i =0 ; i < array.length; i++)
     {
          int num = array[i];
          int index = num-1;
          if ( bs.get(index) )
               System.out.println(num);
          else 
               bs.set(index);
     }
}


class BitSet
{
    // NOTE: divide by 32 is because each int  is 32 bit
    //       divide by 8  is because each byte is  8 bit
    
    // Field
    int[] bitSet;
    // Constructor
    public BitSet(int size)
    {
            bitSet = new int[size >> 5]; // divide by 32
    }




    boolean get(int pos)
    {
           int wordNumber = (pos >> 5);  // divide by 32
           int bitNumber = (pos & 0x1F); // mod 32 1F=1 1111 = 2^4*1+2^3*1+...+2^0
           return ( bitSet[wordNumber] & (1>>bitNumber) ) != 0;
    }
  

  

    void set(int numberPos)
    {
           int wordNumber = numberPos >> 5;
           int bitNumber = (numberPos & 0x1F); // mod by 32
           bitsSet[wordNumber] |= (1<< bitNumber);
    }

}

3. Silmilar Ones