[algogeeks] Re: Missing Number Problem
@Icy: The problem, of course is that there are 900 million 9 digit numbers, so you solved a restricted problem. There is a solution for the given problem. See https://groups.google.com/d/msg/algogeeks/C5oHrps8Q2o/P7tJrhj55ZcJ. Dave On Friday, October 5, 2012 4:26:32 PM UTC-5, icy` wrote: > By "missing" I assume that the numbers are consecutive and we are at > least provided with a range. > > Suppose for the sake of example, the range is 100,000 to 400,000 with > 203,148 being the missing number. They come to us shuffled up, and let us > suppose we are taking them from the hard drive instead of an array, one by > one. Now if the range is known, there is an interesting property of XOR > that you can use. A variable initialized to 0 can be XOR'd with every > element in the range, and then XOR'd with all the provided numbers. It > will then become the missing number. Ruby example (again, assume numbers > coming from hard drive or other source, one at a time, and not array in > memory): > > [image: Inline image 1] > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/arIGbFfpAggJ. 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.
[algogeeks] Re: Missing Number Problem
@Sanjay: This has been discussed before. See https://groups.google.com/d/msg/algogeeks/C5oHrps8Q2o/P7tJrhj55ZcJ for a description of the algorithm. Dave On Friday, October 5, 2012 12:19:40 AM UTC-5, Sanjay Rajpal wrote: > We are given 300 million 9-digit numbers and 2 MB of RAM. We have to find > the missing number. How do we approach this problem ? > > *Regards,* > *Sanjay Kumar* > > > * * > > ** > * > * > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/p-nPQWjDOfkJ. 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.
[algogeeks] Re: Missing Number Problem
By "missing" I assume that the numbers are consecutive and we are at least provided with a range. Suppose for the sake of example, the range is 100,000 to 400,000 with 203,148 being the missing number. They come to us shuffled up, and let us suppose we are taking them from the hard drive instead of an array, one by one. Now if the range is known, there is an interesting property of XOR that you can use. A variable initialized to 0 can be XOR'd with every element in the range, and then XOR'd with all the provided numbers. It will then become the missing number. Ruby example (again, assume numbers coming from hard drive or other source, one at a time, and not array in memory): [image: Inline image 1] -- 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. <>
