Project Euler Problem 4 – Largest palindrome product
02.23.2015
The Problem
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
The Test Case
class Problem4Test < Minitest::Unit::TestCase def test_largest_palindrome_product2 solver = Problem4.new 2 ans = solver.solve assert_equal 9009, ans end end
The Logic
First, find the highest possible product by multiplying the highest two digit factors together. 99 x 99 = 9801.
With highest product, we can iterate backwards and test if it is a palindrome.
If it is a palindrome, we then find its factors that are 2 digits.
Then we check each one to see if the other factor is also 2 digits.
If so, we’ve found our answer.
The Code
class Problem4
def initialize num_digits
@num_digits = num_digits
end
def solve
max_factor = 10**@num_digits - 1
product = max_factor * max_factor
# iterate from max product down to 1
product.downto(1) do |i|
# if it is a palindrome
if is_palindrome i
# get all factors
factors = divisors_of i
# iterate through each factor and divide i by factor
factors.each do |f|
x = i / f
# if x length is equal to num digit, we found our answer
if x.to_s.length == @num_digits
return i
end
end
end
end
return nil
end
def is_palindrome int
str = int.to_s
str == str.reverse
end
# return all factors that are of length num_digit
def divisors_of num
(1..num).select { |n| num % n == 0 && n.to_s.length == @num_digits }
end
end