Welcome to another edition of Jared rediscovers grade school math! Today we are tackling problem 4 of Project Euler. We are going to talk about Palindromes and for loops. Let's get into it!
Problem Discussion
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Video Version
If you like to watch rather than read, check out the video that accompanies this article. If not, keep reading!
Statement
Find the largest palindrome made from the product of two 3-digit numbers.
Palindrome
A word that reads the same forwards as backwards. Example is 9009 or racecar.
Solution
The approach I'm taking is both brute force and algorithmic.
Steps
- Determine the highest products to work from, e.g. 99 x 99
- Multiply the highest products together
- Reduce right number by one
- Check if palindrome
- Repeat until reaching 1
- Reduce left number by one.
- Check if palindrome
- Repeat step 3
- If at any time, number is palindrome, return that number.
Solution
For this solution, I am going to reach for my old friend: functional programming. First let's create a function that checks if a string is a palindrome.
Palindrome?
Our friend Javascript has a ton of helper functions in dealing with strings. Unfortunately, this means that we have to convert our number to a string, then reconvert it back after we've checked it. It takes some extra time, but it's not to computationaly expensive.
function isPalindrome(num) {
// get reverse
let reversed = String(num)
.split('')
.reverse()
.join('');
// return equality check
return Number(reversed) === num;
}
Tale of Two Loops
In order to check all numbers, we have to check all products from 99 x 99 → 1 x 1. To accomplish this, we're going to loop the right number inside of the left number, i.e. 99 x 99 → 99 x 98...and so forth.
function largestPalindromeProduct(n) {
let highest = 0;
// Find largest number
let largestNum = '9';
largestNum += Number(largestNum.repeat(n - 1));
largestNum = Number(largestNum);
// loop left number
for (let i = largestNum; i > 0; i--) {
// loop right number
for (let j = largestNum; j > 0; j--) {
let product = i * j;
// check if palindrome
if (isPalindrome(product)) {
if (product > highest) highest = product;
// we have the highest palindrome for this set, skip to next loop
break;
}
}
}
// return the highest palindrome we found
return highest;
}
Full Solution
function isPalindrome(num) {
// get reverse
let reversed = String(num)
.split('')
.reverse()
.join('');
// return equality check
return Number(reversed) === num;
}
function largestPalindromeProduct(n) {
let highest = 0;
// Find largest number
let largestNum = '9';
largestNum += Number(largestNum.repeat(n - 1));
largestNum = Number(largestNum);
// loop left number
for (let i = largestNum; i > 0; i--) {
// loop right number
for (let j = largestNum; j > 0; j--) {
let product = i * j;
// check if palindrome
if (isPalindrome(product)) {
if (product > highest) highest = product;
// we have the highest palindrome for this set, skip to next loop
break;
}
}
}
// return the highest palindrome we found
return highest;
}
Final Thoughts
This approach includes both a minor algorithm, in that it skips over any numbers below a certain threshold and brute force. It will check all the highest palindromes from 99 x 99 to 1 x 1.
There is definitely room for improvement here. In fact I found a couple out there that are better than mine, but this works for now.
If you have any suggestions or adjustments you think would make it better, feel free to leave a comment!
As always, happy coding.
Resources
https://www.xarg.org/puzzle/project-euler/problem-4/
https://github.com/Matt-1123/project-euler/blob/master/solutions.js
Latest comments (4)
A few possible optimizations:
With both optimizations we go from almost 600k palindrome tests to about 6k tests with largestNum equal to 999.
Hi Dhurak! I think I'm confused by what you mean. In your scenario, what is the
i
value?for (let j = largestNum; j > 0; j--)
can become:
for (let j = i; j > 0; j--)
The inner loop does not have to start from the very beginning every time.
First set would be 99x99, 99x98, 99x97... 99x1
Second set would be 98x98, 98x97, 98x96... 98x1
Third set: 97x97, 97x96, 97x95... 97x1
In second set you don't test 98x99 because you already tested 99x98 in first set.
Ohhh, I see. That's genius. Thank you!