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!

## Friday, September 21, 2012

Subscribe to:
Post Comments (Atom)

hi,,i just want to share link talking about binary number

ReplyDeletehttp://www.math-worksheets.co.uk/141-tmd-what-are-binary-numbers-part-1/

Hi Vincent,

Deletethank you, that's a great link.