Assuming that we know the lower bound and upper bound of the range of
numbers (If not then we can determine it in one pass).
// Solution 1
let lb = lower bound, ub = upper bound, sum = 0;
for each number read from file - sum = sum - number + ub--;
at the end of for loop sum += lb; // This is the missing number.
// Problem with above solution is that the variable sum may overflow if the
contiguous numbers read from the file are very small
// This problem can be solved by changing the second line to this -
for each number read from file -
sum -= number;
if(sum > 0) sum += lb++;
else sum += ub--;
Feedback welcome :-).
- Ravindra
On Sat, Oct 29, 2011 at 9:17 PM, bharat b <[email protected]>wrote:
> @Dave
> Your solution works if the total no.of records(ssn numbers) is 1000
> million.
> But the question states that there are only 300 million numbers.
>
> I think some modification is needed to your answer.
> Correct me if i am wrong.
>
>
>
> On Fri, Oct 28, 2011 at 2:04 AM, Dave <[email protected]> wrote:
>
>> @Shiva: Using an integer array a[100000], initialized to 0, read
>> through the file and for each number n, increment a[n%100000]. At the
>> end of the file, find any k such that a[k] != 10000. Then read through
>> the file again. For any number n such that n%100000 == k, set a[n/
>> 100000] = -1. At the end of file, find any j < 10000 such that a[j] >=
>> 0. Then 100000 * j + k is a number that is missing from the file.
>>
>> Dave
>>
>> On Oct 27, 10:25 am, "shiva@Algo" <[email protected]> wrote:
>> > Given a file containing roughly 300 million social security
>> > numbers(9-digit numbers), find a 9-digit number that is not in the file.
>> > You have unlimited drive space but only 2megabytes of RAM at your
>> > disposal.
>>
>> --
>> 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.
>>
>>
> --
> 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.
>
--
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.
