Algo :
Number of social security numbers possible = 9x10^8 .
300 million = 3x10^8
In these social security numbers duplicates may be present .
1> Take 9 counters and count the social security numbers starting with
1,2,3,...9
2> At the end of 1st traversal , we will know the 1st digit of a
missing number .
Say counter[1] = 1.5x10^8
counter[2] = 8936
and so on .
Thus , a missing number may be of the form 2xx xxx xxx .
3> Now , we make a bitMap of 100 000 000 ( < 2 MB ) . We traverse
through all the numbers and consider only those which are like 2xx xxx
xxx . We switch the corresponding bits ON .
4> Now , we traverse through the bitMap to find 1st OFF bit .
5> We have one 9 digit number which is not present in the input . :)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
