Project Euler 4: Largest palindrome product

Problem

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.

Official Problem

Solution Approach

In this problem of the Largest palindrome product, we have to find the largest palindrome which made up by multiplying two 3 digit numbers.

The solution to this problem is pretty straight forward we will need to use two loops. The outer loop will help in finding one number and the second loop will help in finding the other after multiplication. We also need one condition to check if after the multiplication we get a palindrome or not. Also, we have to check if indeed it is the Largest palindrome product or not.

The time complexity of this approach is O(n²) as we are doing the basic steps inside two loops. The space complexity is O(1) as we need one variable to store the Largest palindrome product.

Coming to the coding part for this approach, we initialize a variable to store the result. Then we loop twice in nested fashion starting from 100 to 999 as we need only 3 digit number. Then we multiply the corresponding numbers and find out if they are palindrome or not. In case they are palindrome, then we find if they are greater than the result or not. Again if it is so, we change the result to contain the current maximum value which is also a palindrome. In the end, we return this result variable as the answer.

Solution Code

Python Solution

def largest_palindrome_product():
	result = max(i * j
		for i in range(100, 1000)
		for j in range(100, 1000)
		if str(i * j) == str(i * j)[ : : -1])
	return str(result)
	
print(largest_palindrome_product)

def largest_palindrome_product():

result = max(i * j

for i in range(100, 1000)

for j in range(100, 1000)

if str(i * j) == str(i * j)[ : : -1])

return str(result)

print(largest_palindrome_product)

Java Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution
{
	public static void main (String[] args) 
	{
		int maxPalin = -1;
		for (int i = 100; i < 1000; i++) {
			for (int j = 100; j < 1000; j++) {
				int prod = i * j;
				if (isPalindrome(prod) && prod > maxPalin)
					maxPalin = prod;
			}
		}
		System.out.println(Integer.toString(maxPalin));
	}
	
	public static boolean isPalindrome(int number){
		String stringNumber = String.valueOf(number);
		StringBuilder reverseStringNumber = new StringBuilder(stringNumber);
		return stringNumber.equals(reverseStringNumber.reverse().toString()) ;
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Solution

{

public static void main (String[] args)

{

int maxPalin = -1;

for (int i = 100; i < 1000; i++) {

for (int j = 100; j < 1000; j++) {

int prod = i * j;

if (isPalindrome(prod) && prod > maxPalin)

maxPalin = prod;

}

System.out.println(Integer.toString(maxPalin));

}

public static boolean isPalindrome(int number){

String stringNumber = String.valueOf(number);

StringBuilder reverseStringNumber = new StringBuilder(stringNumber);

return stringNumber.equals(reverseStringNumber.reverse().toString()) ;

}

For more Project Euler explained solutions visit Project Euler Detailed Solutions.

For Leetcode detailed solutions go to Leetcode Detailed Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Coding 🙂

Problem

Solution Approach

Solution Code

Python Solution

Java Solution

Leave a Comment Cancel Reply