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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.