-
Notifications
You must be signed in to change notification settings - Fork 1
/
4.hs
24 lines (18 loc) · 843 Bytes
/
4.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
-- 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.
-- 999*999 = 998001
-- O(x*y*z) = 9 * 10 * 7 = 630
-- Because we are computing up-down, it's likely
-- to find the solution before we'll check all palindromes
palindromes = [x*100000 + y*10000 + z*1000 + z*100 + y*10 + x | x <- [9,8..1], y <- [9,8..0], z <- [7,6..0]]
-- O(n) = 1000
threeFactors' x 1000 = False
threeFactors' x y = x `mod` y == 0
&& between (x `div` y) 100 999
|| threeFactors' x (y + 1)
where between x y z = y <= x && x <= z
threeFactors x = threeFactors' x 100
result = head . dropWhile (not . threeFactors) $ palindromes
main = putStrLn . show $ result