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?

When curiosity outbursts …!!!

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?

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

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

Still better algorithms exists than urs, pawpro.

Pa1

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