# Project Euler #4 - Largest Palindrome Product

### Peter Kim Frank twitter logo github logo May 28 '19・1 min read

Project Euler (7 Part Series)

I'm bumping a "series" that I started last year, where we collectively work on problems from Project Euler.

This is Problem 4, finding the largest palindrome product.

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.

DISCUSS (31) Here's my Python solution!

``````def palindrome_number():
_range = xrange(100, 1000)
palindrome = None
for i in _range:
for j in _range:
prod = i * j
if str(prod) == str(prod)[::-1]:
if prod > palindrome:
palindrome = prod
return palindrome

print(palindrome_number())
``````

How's the run time? I think yours is Python 2?

Here's mine in Python 3 :) It's a bit more complicated because I try to write them more flexible. Like how this problem shows 2 digit numbers as an example and 3 for the actual problem, so I wrote it to take the number of digits per number as an input

``````import time
def largestPalindromeProduct(digits):
min, max, temp, pal = '1', '', 0, 0
for _ in range (1,digits):
min += '0'
for _ in range (0,digits):
max += '9'
min = int(min)-1
max = int(max)
start = time.time()
for num1 in range (max,min,-1):
for num2 in range (num1,min,-1):
temp = num1 * num2
if temp < pal:
break
if str(temp) == "".join(reversed(str(temp))):
pal = temp
end = time.time()
print(pal, end=' ')
print(end-start)
``````

A naive F# implementation:

``````let reverse (s : string) = s |> Seq.toArray |> Array.rev |> System.String

let palindrome n = let s = string n in s = reverse s

[<EntryPoint>]
let main _ =
seq { for i = 100 to 999  do
for j = 100 to 999 do
let p = i * j
if palindrome p then yield p }
|> Seq.max
|> printf "%d\n"
0
``````

Runs reasonably fast with .NET Core on my Macbook Air:

``````\$ time dotnet Euler4.dll
906609
dotnet Euler4.dll  0.35s user 0.03s system 101% cpu 0.376 total
``````

This is another solution that I consider working in this particolar case (3 digits) but not actually correct (granted I could understand F# 😅). I explained it here: dev.to/maxart2501/comment/b9me

This code generates the sequence of all palindromes which are products of 3 digit numbers and then selects the largest with `Seq.max`, so it does indeed produce the correct solution (just verify it on the Project Euler website).

You were right though about the Ruby version in your other comment. On a side note though: maybe don't go around telling people their code might be wrong if you can't actually understand the language it's written in?

I'm sorry if that seemed rude, that wasn't my intention at all. I did add "granted I could understand F#" in case I was wrong.

But no, I will keep on trying to understand what's going on in other people's code even out of my comfort zone, because I'll have the chance to learn something new 👌

If your intention really is to learn then you'd be better of asking questions (e.g. "I don't know F#, would you mind explaining how this selects the biggest palindrome?") instead of making statements that need a qualifier of potentially being wrong.

Being wrong is nothing to be ashamed of, as long as you're ready to stand corrected.

My mistake in this case is that I commented while it was very late 😴 Took note on the approach, though.

A quadratic solution in JavaScript. I'm curious if there's a way to do this in linear time:

``````const array = new Array(900).fill(0).map((e, i) => i + 100);

const isPalindrome = num => {
return (
String(num) ===
String(num)
.split("")
.reverse()
.join("")
);
};

const maxProduct = range => {
let palindrome = 0;
for (let i = 0; i < range.length; i++) {
for (let j = i + 1; j < range.length; j++) {
const product = array[i] * array[j];
if (isPalindrome(product) && product > palindrome) {
palindrome = product;
}
}
}

return palindrome;
};

console.log(maxProduct(array));
``````

Not linear... but I think (without any actual proof 🤷‍♂️) (I'm a fraud 🤦‍♂️) that my solution does it in logarithmic time: dev.to/maxart2501/comment/b9m6

Edit: scratch that, no way it's not quadratic 😂 But then again, it's faster than the extensive check.

Here's my Ruby solution. There's probably a much more clever way to do this. Probably a more Ruby way to do it for that matter.

``````# Find the largest palindrome number that is the product of two three digit factors.

def check_equality(num)
num.to_s == num.to_s.reverse
end

def find_palindrome
r1 = (999..1)
r2 = r1

(r1.first).downto(r1.last).each do |i|
(r2.first).downto(r2.last).each do |j|
if check_equality( i * j )
puts "#{i} * #{j} = #{i*j}"
return
end
end
end
end

find_palindrome
``````

If I understand it correctly (correct me if I'm wrong, I don't know Ruby), this doesn't work in general, as it prints the first palindrome product you find. But you don't know if it's the largest.

Unless you can prove it is 🤷‍♂️ (I have no idea).

I'm working backwards through the range of numbers beginning with '999.' Hence the extra verbosity in the block with the call to the downto method. (999..1).each do doesn't work, and (1..999).each do really shouldn't work either because ranges are not defined by their content, just a beginning state and an end state. So counting backwards the first palindrome I find is the largest. And the outer block isn't necessary, but I include it just for the sake of being thorough I guess.

The problem here is that the products you're getting aren't ordered. Which means that if you get a palindrome, you cannot be sure it's the largest.

In fact, I run your code and I got `999 * 91 = 90909`, which is not correct. Even if you limit your range to 999 to 100 (we're looking for 3-digit factors after all), you'd get `995 * 583 = 580085`. But the largest palindrome is `993 * 913 = 906609`, which comes after the others.

Here is my code on C (Brute force), the result was out after 0.172s.

``````#include <stdio.h>
#include <stdlib.h>

int palindrome(long x)
{
int i,j=0;
char ch;
sprintf(ch,"%ld",x);

char ch1="";
for(i=strlen(ch)-1;i>=0;i--,j++)
{
ch1[j]=ch[i];
}

if(strcmp(ch,ch1)==0)
return 1;
return 0;
}

int main()
{
int i,j;
long s,max=100*100;
for(i=100;i<=999;i++)
{
for(j=100;j<=999;j++)
{
s=i*j;
if (palindrome(s) && s>max)
max=s;
}
}
printf("Result = %ld",max);
}
``````

Enhanced:

``````/****** 0.128 s *******/
for(i=999;i>=100;i--)
{
for(j=999;j>=100;j--)
{
s=i*j;
if (palindrome(s))
{
if(s>max)
max=s;
break;
}
}
}
``````

Just did this super quick in JS.

``````function isPalindrome(num) {
const stringifiedNum = num.toString();

return (
Array.from(stringifiedNum).toString() ===
Array.from(stringifiedNum)
.reverse()
.toString()
);
}

function findLargestPalindrome() {
const start = 100;
const end = 999;

let largestPalindrome = 0;

for (let i = start; i <= end; i += 1) {
for (let j = start; j <= end; j += 1) {
const product = i * j;
if (isPalindrome(product) && product > largestPalindrome) {
largestPalindrome = product;
}
}
}

return largestPalindrome;
}

findLargestPalindrome();
``````

Yes. Let's try reading it step by step:

1. We first check if the product is a palindrome. Because if it isn't, we don't care about it.
2. Then, we check if it is greater than our existing largest palindrome because our goal is to find the largest palindrome.
3. If both those conditions are true, the product being a palindrome and it being larger than our existing largest palindrome, we set that as our largest palindrome.

Hope that helps, let me know if you still have questions!

My typescript solution:

``````function reverseInteger(n: number): number {
return Number(String(n).split('').reverse().join(''));
}

function isPalindrome(num: number): boolean {
if (num === reverseInteger(num)) {
return true;
}
return false;
}

// I had this in separate files sorry if its confusing X)
import { max } from 'mathjs';

let number = 0;
let a = 999;

const palindromes: number[] = [];

while (a > 1) {
for (let i = 2; i <= 999; i += 1) {
number = a * i;
if (isPalindrome(number)) {
palindromes.push(number);
}
}
a -= 1;
}
console.log(`Max palindrome \${max(...palindromes)}`);
``````

``````if (condition) {
return true;
}
return false;
``````

Please don't do this 😕 It's verbose for no reason. You can accomplish the same with just `return condition;`.

Here is freeCodeCamp version of it

``````
function largestPalindromeProduct(n) {
// Good luck!
const isPalindrom = n => {
return String(n).split("").reverse().join("") === String(n);
}
let largestPalindrome = 0;
const lowerBound = Number(`1\${Array.from({length:n}).join(0)}`);
const upperBound= Number(`\${Array.from({length: n+1}).join(9)}`);
console.log({upperBound, lowerBound})
for(var i=lowerBound; i<=upperBound; i++) {
for(var j=lowerBound; j<=upperBound; j++) {
const product = i*j;
if(isPalindrom(product) && product > largestPalindrome ) {
console.log(i, j, product, largestPalindrome)
largestPalindrome = i*j;
}
}
}
return largestPalindrome;
}

largestPalindromeProduct(2);
``````

Am still able to just copy and paste from my Euler GitHub repo. 😂

PHP again

``````\$largestThreeDig = 999;
\$largestPalindrome = 0;
for(\$l = \$largestThreeDig; \$l > 0 && \$l * \$largestThreeDig > \$largestPalindrome; \$l--) {
for(\$p = \$l * \$largestThreeDig; \$p > \$largestPalindrome; \$p -= \$l) {
if((string)\$p === strrev((string)\$p)) {
\$largestPalindrome = \$p;
}
}
}
echo "Largest Palindrome: \$largestPalindrome\n";
``````

This is another solution that I consider working in this particular case (3 digits) but not actually correct in the general case. I explained it here: dev.to/maxart2501/comment/b9me

This is my solution in Javascript

function largestPalindromeProduct(n) {
let num = "1"
let lNumber = 0
for(let i = 0; i < n; i++){
num = `\${num}0`
}
num = parseInt(num)
let rangeNum = num.toString().replace("0","")
lNumberLoop:
for(let i = num; i > 0 ; i--){
for(let j = i; j > i - rangeNum; j --){
let number = (i * j)
let revN = parseInt(number.toString().split("").reverse().join(""))
if(number === revN && revN.toString().length % 2 === 0){
lNumber = number
break lNumberLoop
}
}
}
return lNumber
}

console.log(largestPalindromeProduct(2));

Love to work on the challenges, please keep this series running.
Here's my Rust Solution: Playground

``````fn main() {
let max = max_palindrome();
println!("Max palindrome is {}, product of {} * {}", max.1, (max.0).0, (max.0).1);
}

fn max_palindrome() -> ((i32, i32), i32) {
let range = 100..1000;
let mut ans = ((0, 0), 0);
for a in range.clone() {
for b in range.clone() {
let p = a * b;
if is_palindrome(p) && p > ans.1 {
ans.1 = p;
ans.0 = (a ,b);
}
}
}
ans
}

fn is_palindrome(num: i32) -> bool {
let str_num = num.to_string();
str_num
.chars()
.zip(str_num.chars().rev())
.all(|(c1, c2)| c1 == c2)
}

``````

Sooo... there are so many good solutions, but they all kind of look the same, so I wanted a different approach 😁

What if, instead of starting with the factors and checking if their product is a palindrome, we start with palindromes and find two 3-digit factors?

We'd start with 999999, then 998899, then 997799... You get the point. So we can start with a 3-digit number (e.g. 356)... and get a palindrome out of it (e.g. 356653), and look for factors.

My solution in JavaScript:

``````const digits = 3;
const upper = 10 ** digits - 1;   // 999
const lower = 10 ** (digits - 1); // 100
function palindromize(num) {
}

let p, b;
out: for (let a = upper; a >= lower; a--) {
p = palindromize(a);
for (b = Math.floor(p ** .5); p/b <= upper; b--) {
if (p % b === 0) break out;
}
}
console.log(p / b, b);
``````

I've tested it with up to 7 digits and it's still basically instantaneous. Over that limit you go over `Number.MAX_SAFE_INTEGER` and it becomes unreliable. I didn't bother using `BigInt`s, also because you can't get the square root out of them (you can approximate it, but it's a bother).

P.S.: yes, I've used a label in JavaScript. Sue me 😂 (also useful if you have to break out of more than one cycle... which is usually rare).

Written in Java!

``````public class Problem4 {
public static boolean isPalindrome(long val) {
boolean isPalindrome = true;
String str = Long.toString(val);
int len = str.length();
int i = 0;
while (isPalindrome && i <= (len-1)/2){
isPalindrome = str.charAt(i) == str.charAt(len-1-i);
i++;
}
return isPalindrome;
}

public static void main(String[] args) {
int i = 999;
long largest = 1;
String str = "";
long val = 1;
while (i>=100)
{
int j = i;
while (j>=100)
{
val = i * j;
if(isPalindrome(val) && largest < val)
{
largest = val;
str = i + " x " + j;
}
isPalindrome (val);
j--;
}
i--;
}
System.out.println(str+ "= "+ largest);

}
}
``````

a lazy c++ solution :)

``````auto larget_palindrome_product(size_t n_digits) -> size_t {

const auto is_palidrome = [](size_t x) -> bool {
const auto as_string = std::to_string(x);
auto fst = as_string.begin();
auto lst = as_string.rbegin();
for (; fst != as_string.end(); fst++, lst++)
if (*fst != *lst) return false;
return true;
};

size_t result = 0;
const auto lower_bound = std::pow(10, n_digits - 1);
const auto upper_bound = std::pow(10, n_digits) - 1;

for (size_t fst = lower_bound; fst <= upper_bound; fst++) {
for (size_t snd = fst; snd <= upper_bound; snd++) {
if (auto n = fst * snd;
is_palidrome(n) && n > result) {
result = fst * snd;
}
}
}

return result;
}
``````

Classic DEV Post from Apr 1 '19

## What's your favorite coding joke/comic etc? Sore eyes?

dev.to now has dark mode.

Go to the "misc" section of your settings and select night theme ❤️  