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?
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?
3 responses so far ↓
1 pawpro // Nov 30, 2008 at 6:25 pm
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 Pa1 // Nov 30, 2008 at 11:33 pm
But time complexity is more than O(N^2).
Still better algorithms exists than urs, pawpro.
Pa1
3 Pa1 // Nov 30, 2008 at 11:36 pm
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
Leave a Comment