DEV Community

Peter Kim Frank
Peter Kim Frank

Posted on

Project Euler #4 - Largest Palindrome Product

#projecteuler #challenge

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.

Latest comments (36)

Collapse
 
rossman profile image
Rossman •

C#

    internal class Task4
    {
        public static string Reverse(string s)
        {
            char[] charArray = s.ToCharArray();
            Array.Reverse(charArray);
            return new string(charArray);
        }

        private bool IsPalindrome(int number) 
        {
            string strNumber = number.ToString();
            string reversedStrNumber = Reverse(strNumber);
            return strNumber == reversedStrNumber;
        }
        public Task4() 
        {
            int maxPalindrome = int.MinValue;
            for(int i = 999; i > 99; i--) 
            {
                for (int j = 999; j > 99; j--)
                {
                    int result = i * j;
                    if (result > maxPalindrome && IsPalindrome(result))
                        maxPalindrome = result;
                }
            }
            Console.WriteLine(maxPalindrome);
        }
    }
Enter fullscreen mode Exit fullscreen mode
Collapse
 
starchcode profile image
starchcode •

here is my result using JS. avoided any use of methods. Also not a master in mathematics but here it is

Collapse
 
handsomespydie profile image
SpyDie • • Edited

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.

This is the easiest way and logical too.. 

list = []

for i in range(901,1000):
    for j in range(901,1000):
        prod = i*j
        if str(prod) == str(prod)[::-1]:
            list.append(prod)

    i += 1
    j += 1

list.sort()

print(list[-1])
Collapse
 
shyam1110 profile image
shyam1110 •

Complete Solution..!!! for Euler 004

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

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

    }
}
 
maxart2501 profile image
Massimo Artizzu •

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.

 
maxart2501 profile image
Massimo Artizzu •

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 👌

Collapse
 
maxart2501 profile image
Massimo Artizzu •

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

Collapse
 
maxart2501 profile image
Massimo Artizzu • • Edited

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

View full discussion (38 comments)

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

Read next

codeisgood profile image

Invoking an AWS Lambda Function with Terraform

codeisgood -

conduct2024 profile image

Couldn’t get equations in html when convert word .docx file to html file in C#.

conduct2024 -

maneh profile image

What is Smart Play Apk?

maneh -

elainecbennet profile image

What Makes a Winning SaaS Landing Page? A Comprehensive Guide

Elaine Bennett -