Find duplicate integer in an large integer array | Hello World

Find duplicate integer in an large integer array | Hello World
You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4KB of memory available, how would you print all duplicate elements in the array?
4KB memory = 4*8*2^10 bits, which is larger than the 32000, so we can map each integer to one bit and count the duplicates.
The java only support granularity of bytes, so in order to do bit operation, we need to implement bitSet of our own. Here is a sample of implementation, the divide operation could be replaced by bitshift operation.

public class BitSet {

    int [] bitSet;

    public BitSet(int size) {

        bitSet = new int [size/4]; // use integer array to store bitset

    }

     

    public void set(int pos){

        int wordNum = pos/32;

        int offSet = pos%32;

        bitSet[wordNum] |= (0x1 << offSet);

    }

     

    public boolean get(int pos) {

        int wordNum = pos/32;

        int offSet = pos%32;

        return (0x1 & (bitSet[wordNum] >> offSet)) != 0;

    }

}

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/BitSet.java
Read full article from Find duplicate integer in an large integer array | Hello World