You have 1000 integers. All are less than 1000 and greater or equal to 1. Among them, 999 are distinct and there is one that is found twice. How can you find the duplicate?

3 thoughts on “You have 1000 integers. All are less than 1000 and greater or equal to 1. Among them, 999 are distinct and there is one that is found twice. How can you find the duplicate?”

1. pawpro

   16 years ago

   Sort the list and then loop removing duplicates (if current and next are equal remove next). Memory complexity is close to O(N) for any big N-s

   Reply
2. Pa1

   16 years ago

   But time complexity is more than O(N^2).

   Still better algorithms exists than urs, pawpro.

   Pa1

   Reply
3. Pa1

   16 years ago

   1st question answer would be:

   Take the sum of the given numbers and also sum of first 1000 natural numbers, difference of these two get the number with duplicate.

   for 2nd question, the above approach won’t work as sum can’t be stored in 32-bit number. Try to solve this algorithm by your own.

   Pa1

   Reply