def sum_of_digits(n) sum = 0 while (n > 0) sum += n % 10 n /= 10 end sum end
num_digits = gets.chomp.to_i
exponent = num_digits/2 divisor = 10**exponent
limit = (10**num_digits) - 1 total = 0
0.upto(limit) do |cur| upper = cur / divisor lower = cur % divisor total += 1 if sum_of_digits(upper) == sum_of_digits(lower) end
For 2, 4 and 6 digits it got the requisite answers of 10, 670, and 55252. There was a bit of a pause while it crunched away at the 6-digit case, though.
For 8 digits it … well, I let it run and went to do something else. Then I had the bright idea to time it (on mac OS X, using the time command):
real 1m42.596s user 1m34.222s sys 0m1.837s
The right answer, but the last time I checked, one minute anything was greater than two seconds. What to do?
It’s pretty clear that calling sum_of_digits a bunch more times than necessary is the biggest problem. For try #2, I precomputed the sums and stuffed them into an array, and indexed the array in place of calling sum_of_digits in the main loop. Here’s the result:
time ruby lucky.rb < t8.txt 4816030
real 0m19.176s user 0m18.017s sys 0m0.313s
A better than 80% speedup. Most times I would kill for that, but I still need to lose 95% of the remaining run time. How to do it?
I checked … initializing the array of sums takes virtually no time, even if I write out the entire array contents to a file.
So the main loop is killing me, and unfortunately I need a dramatic change of algorithm but I don’t see one. So …
1. Recode in C or C++ 2. Hell if I know
Taking option 1, I got Accepted, with run times around 1.1 seconds or so for 8 digits. It's a straightforward translation to C++, very brute force.