Find duplicate integer in an large integer array

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;
	}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s