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?

Extension to this questions is – if there are some billion numbers are there, and you have enough memory to fit all these numbers. What is the best of to do the same?

Categories Uncategorized

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. 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

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

Still better algorithms exists than urs, pawpro.

Pa1

3. 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