[ProjectEuler] Brute force just won’t do
Sometimes simply getting the code to work won’t do it.
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
— Project Euler Problem 5
Initially, I came up with
arr = (2..20).to_a
counter = 10
arr_modulo = []*10
while arr_modulo != [0]*10
counter = counter + 1
arr_modulo = arr.map {|n| counter % n}end
puts counter
This code works by manually checking whether each number starting from counter is divisible with everything inside array arr. It works fine — as long as the solution is relatively small. If arr was (2..10), then it calculates within a few seconds. If arr was (2..20) however, my macbook air could not handle it. The solution was in hundreds of millions, about ten-thousand times the solution as if arr was (1..10).
I learned that there will come a time when simply getting a working code does not do it. It’s like buying a vehicle that gets to point A to point B, but can’t go more than 35 mph.
A faster solution is required. After searching and thinking and mostly googling, I found another solution — solution so simple it is almost cheating.
(1..20).inject(:lcm)
It took ruby less time to compute the code above than my initial code with arr of (1..10). The code above utilized Ruby’s least common multiple (lcm) built-in method to automatically find common multiple (always positive) of given argument, combined with inject method.
