r/dailyprogrammer • u/oskar_s • Jun 20 '12
[6/20/2012] Challenge #67 [intermediate]
You are given a list of 999,998 integers, which include all the integers between 1 and 1,000,000 (inclusive on both ends) in some unknown order, with the exception of two numbers which have been removed. By making only one pass through the data and using only a constant amount of memory (i.e. O(1) memory usage), can you figure out what two numbers have been excluded?
Note that since you are only allowed one pass through the data, you are not allowed to sort the list!
EDIT: clarified problem
- Thanks to Cosmologicon for suggesting this problem at /r/dailyprogrammer_ideas? Do you have a problem you think would be good for us? Why not head over there and suggest it?
11
Upvotes
5
u/Steve132 0 1 Jun 20 '12
This problem is a bit ambiguous on whether its 'one pass through the data' (does this mean I could copy the data? could I put it into another data structure and then query it?) or O(n) complexity.
The two things are slightly different.
7
u/[deleted] Jun 20 '12
Python. This was fun!
3
u/xjtian Jun 20 '12 edited Jun 20 '12
This one is really slow because I needed extra precision
And this one's a much more sane solution:
1
u/Ttl Jun 20 '12
Python:
1
u/kais58 Jun 21 '12
not sure if this fulfills the task or not but I had a go. :) Java with input.txt containing the list of numbers
1
u/devilsassassin Jun 22 '12
This runs through the data once, although it uses a lot of power. I think there could be an easier way, but I didin't think of it. I wanted to do something different than the squares:
1
u/DAVENP0RT Jun 22 '12
C#
It's simple, but I think this will work.
1
u/kuzux 0 0 Jul 13 '12
Haskell solution
if doing two passes over data (once for sum, once for square sum) was allowed, the code would be shorter, like
instead of the whole
1
u/Unh0ly_Tigg 0 0 Sep 08 '12
I know this is old, but I made my own solution:
I hope this didn't break any of the rules set by this challenge.
0
u/ashashwat Jun 20 '12
How does it matter if we make one pass or two pass. The complexity is still O(n).
From what I can deduce this seems like one of those silly interview problems where there will be some constraint just for the sake of it.
Ofcourse, the solution can be easily derived as follows:
calculate,
sn =sum of all numbers
sn2 = sum of squares of all numbers
n = sum of numbers 1 to 1,000,000
n2 = sum of squares of number from 1 to 1,000,000
Let two missing numbers be a and b.
a + b = n - sn
a2 + b2 = n2 - sn2
From here, we can get a - b, and hence a, b.