Tuesday, 29 May 2012

Find the duplicate in an array of numbers from 1 to 1000

I. Given an array of 1001 integers with number from 1..1000, and one of the numbers duplicated. How would you find the duplicate in the array.

-> (Sum of Array)-(Sum of number from 1..1000) = duplicate number
-> XOR of all numbers from 1 to 1024 is zero. So, XOR all numbers in the array, plus the numbers from 1001..1024. The duplicate number is produced as the output.

II. What if the array has 1002 integers with two different numbers as duplicates. How would you find both the duplicates ?

-> This one is based on the lines of the XOR solution above. Find the XOR.
In this XOR value, each '1' bit represents the position where the two duplicates differ.
So make two sets of numbers, one in which this bit position is set and another with this bit unset.
Take the XORs separately for one set of elements in which a particular bit is set, this will give you one element. XORing the elements with the bit unset will give you the other element.


code: qor:{((x&y)~:)&x|y}

No comments:

Post a Comment