Suppose you have an array of 99 numbers representing the integers from 1 to 100, unordered, with one missing. What's the most efficient way to find and return the missing number?
You save one operation if you just subtract from 5050 as you go, and that feels cleaner. I don't know if there's a significant performance difference between addition and subtraction, enough to overcome the additional operation.
If subtracting ninety-nine times introduces too much overhead, you could try starting at -5050 and adding. You'll have to reverse the sign at the end, which might be as expensive as the subtraction I proposed. This also doesn't feel very clean.
7 comments:
Add 'em up, subtract from 5050?
Natch.
You save one operation if you just subtract from 5050 as you go, and that feels cleaner. I don't know if there's a significant performance difference between addition and subtraction, enough to overcome the additional operation.
If subtracting ninety-nine times introduces too much overhead, you could try starting at -5050 and adding. You'll have to reverse the sign at the end, which might be as expensive as the subtraction I proposed. This also doesn't feel very clean.
Of course now I'm trying to figure out the optimal solution if two numbers are missing from the group instead of just one ;)
That's a much more interesting question. Here's a first cut with only one loop through the array:
def find_it(ninetyeight)
#one hundred 1 bits
big = 2**100 - 1
#log base 10 of two (for conversion)
convert = Math.log(2)
#Bitwise or each int in the array with our big int
ninetyeight.each {|one| big ^= (2**(one - 1))}
#Get the first remaining 1 bit
first = big & -big
#Bitwise or the first one out, leaving the second
second = big ^ first
#Get the logs base two, not forgetting to add 1,
#and return them.
return [(Math.log(first) / convert + 1).to_i, (Math.log(second) / convert + 1).to_i]
end
This would be pretty easy to generalize by just iterating that "first = big & -big" line until you're out of powers of two.
By "generalize" I meant, "generalize to n missing integers".
Oh, and in the comments read "bitwise or" as "bitwise xor".
Post a Comment