DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Peter Kim Frank
Peter Kim Frank

Posted on

Project Euler #4 - Largest Palindrome Product

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.

Top comments (38)

Collapse
 
aspittel profile image
Ali Spittel

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())
Collapse
 
justinenz profile image
Justin • Edited on

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)
Collapse
 
mamounbs profile image
Mamoun Boussida • Edited on

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[7];
    sprintf(ch,"%ld",x);

    char ch1[7]="";
    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);
}
Collapse
 
farazpatankar profile image
Faraz Patankar

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();
Collapse
 
1258632 profile image
by

while there are many explanations, easiest to understand was yours. the only part I struggle to understand is this one "isPalindrome(product) && product > largestPalindrome", can you please explain what it means?

Collapse
 
farazpatankar profile image
Faraz Patankar

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!

Thread Thread
 
1258632 profile image
by

Thank you, Faraz, I didn't know it was possible to use several conditional operators in one single line of code

Collapse
 
silvestricodes profile image
Jonathan Silvestri

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));
Collapse
 
maxart2501 profile image
Massimo Artizzu • Edited on

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.

Collapse
 
flrnd profile image
Florian Rand • Edited on

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)}`);
Collapse
 
maxart2501 profile image
Massimo Artizzu
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;.

Collapse
 
flrnd profile image
Florian Rand

cool! yes so much simple

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

thanks!

Collapse
 
noblebe4st profile image
Jeff Hall

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
Collapse
 
maxart2501 profile image
Massimo Artizzu

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).

Collapse
 
noblebe4st profile image
Jeff Hall

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.

Thread Thread
 
maxart2501 profile image
Massimo Artizzu

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.

Collapse
 
ib250 profile image
Ismail Bello

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;
}
Collapse
 
prabh profile image
Prabhjot Singh Rana • Edited on

Solution in Python:

x = 0   # assuming number is Xnnnnn  1st digit
y = 0   # assuming number is nYnnnn  2nd digit
z = 0   # assuming number is nnZnnn  3rd digit

num = 999  #highest 3 digit number

palidromefound = False

highestnum = num * num

while str(highestnum) != str(highestnum)[::-1]:

    z = int(highestnum / 1000)
    z = z%10

    y = int(highestnum / 10000)
    y = y%10

    x = int(highestnum / 100000)
    x = x%10

    if z != 0 and y != 0:
        z = z-1

    # first time find the highest palidrom

    highestnum = (x*100000 + y*10000 + z*1000 + z*100 + y*10 + x)


while palidromefound == False:

    if str(highestnum) == str(highestnum)[::-1]:
        while num > 99:

            if (highestnum % num) == 0 and (highestnum / num) < 999 and (highestnum / num) > 99:
                palidromefound = True
                print(f'Highest Palidrom: {highestnum} num1: {num} and num2: {int(highestnum / num)}')
                break
            num = num -1

        else:

            num = 999

            # below are the palidromes.. the value of z is the 3rd digit, it comes from the above logic
            # when the first highest palidrom is found, but if it not a multiple of two three digit numbers
            # then the next highest palidrome is obtained:
            #
            # 992299 - 1100 = 991199  >> when z != 0
            # 991199 - 1100 = 990099  >> when z != 0
            # 990099 - 110  = 989989  >> when z == 0
            # 989989 - 1100 = 988889  >> when z != 0 


            if z == 0:
                highestnum = highestnum -110
                z = 9
            else:
                highestnum = highestnum -1100
                z = z-1
Collapse
 
jay profile image
Jay

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)
}

Collapse
 
seyedmahmoudbayazid profile image
Mahmoud Bayazid

First observation is that the number must be between 100^2 and 999^2 or in the range of [10000, 998001].

As the majority of numbers has 6 digits and we're looking for the largest, we ignore 5 digits numbers.

Based on this, we can construct a palindromic number as:

'abccba' =100000a+10000b+1000c+100c+10b+a

=100001a+10010b+1100c

=11(9091a+910b+100c) = p.q

This equation shows us, that either p or q, but not both must have a factor of 11!!!

def palindrome_number(x,y):

my_list =[]

for i in range(x,y):
    for j in range(x,y):
        num = i * j
        if num % 11 ==0 and str(num) == str(num)[::-1]:
            my_list.append(num)
            my_list.sort()

print(my_list[-1])
Collapse
 
shyam1110 profile image
shyam1110

void solve()
{
fast;
ll n,largepalin=0;
cin>>n;
for(ll i=999;i>=100;i--)
{
for(ll j=999;j>=100;j--)
{
if((i*j)%11==0 && palin(i*j) && (i*j)<n) largepalin=max(i*j,largepalin);
}
}
cout<<largepalin<<endl;
return;
}

Collapse
 
shahidcodes profile image
Shahid Kamal Khan

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);
Collapse
 
vienpham2019 profile image
vienpham2019

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));

Collapse
 
khouloudzaiter profile image
khouloudzaiter

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);

    }
}
Collapse
 
maxart2501 profile image
Massimo Artizzu • Edited on

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) {
  const padded = String(num).padStart(digits,'0');
  return +(padded + padded .split('').reverse().join(''));
}

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 BigInts, 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).

Collapse
 
stephanie profile image
Stephanie Handsteiner

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";
Collapse
 
maxart2501 profile image
Massimo Artizzu

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

Some comments may only be visible to logged-in visitors. Sign in to view all comments.

🌚 Friends don't let friends browse without dark mode.

Sorry, it's true.