## 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```

https://github.com/travisluong/projecteuler