Friday, September 21, 2012

Finding duplicate numbers with Binary Math in Java

I went for an interview once, and was asked the following question:

Given a sequence of numbers, from 1 to 1000, where only one number is duplicated, how would I proceed to find the duplicate number?

After I solved the problem using a basic loop that just checks if it's seen this number before using a hash table, the interviewer asked if I could improve my answer using XOR math. I didn't quite get it right, this is the solution they showed me :

int numbers[] = {4,2,3,4,5,6,7,8,1,10,11,12,13,14,9};

for (int pos = 1; pos < numbers.length; pos++)
{
  numbers[pos] = numbers[pos] ^ numbers[pos-1] ^ pos;
}

System.out.println("Duplicate is : " + numbers[numbers.length-1]);


This bit of Java code loops through the array and finds the duplicate number. Of course, this only works for positive integers, I've not tested it with negative numbers and I know it doesn't work with floats.

So, there you go, a good use for binary math in Java!

1 comment: