Project Euler : Problem 4 - Largest palindrome product
Problem Statement : Largest palindrome product
Problem 4 : A palindromic number reads the same both ways. The largest palindrome made from the product of two -digit numbers is . Find the largest palindrome made from the product of two -digit numbers.
Concept and Theory
All I have to say is, its a very beautiful problem. Before we start lets have some theory. So, a palindrome is a something which when read forward or backwards remains the same, for eg, or , but here we are talking about math not English words. Is there something unique about these palindromic numbers ? Yes they do, all palindromic numbers of even length are divisible by . We will see later why is it so.
Naive Approach
A naive approach will be to start a sequence from till increasing by one at a time and start another sequence from till decreasing one at a time. We will take one number from each sequence and multiply them and see if the result is a palindrome or not. Every time we find a product which is palindrome we will update our result based on the fact that the current found number is greater than previous palindromic number or not. One can point out that we are doing some double calculations, since we have pairs, product of will be same as . Also one will say since we have to find out the largest why not start both the sequence from and go backwards. So we can optimize our code.
Code
/**
* A function to reverse a number
*
* @param num
* given input number
* @return reverse of that number
*/
public static int reverseNumber(int num) {
int reverse = 0;
while (num != 0) {
reverse = reverse * 10 + (num % 10);
num /= 10;
}
return reverse;
}
/**
* A function to check if a number is palindrome of not
*
* @param num
* given input number
* @return a boolean value of true is the number is palindrome else false
*/
public static boolean isNumberPalindrome(int num) {
return num == reverseNumber(num);
}
/**
* A function to find largest palindrome product below a given certain number
*
* @param num
* : limit unders which we need to find our product
* @return largest palindromic number which can be written as product of two 3
* digit numbers
*/
public static int naiveLargestPalindromeProduct(int num) {
int largestPalindromicProduct = 0;
for (int numberA = 999; numberA >= 100; numberA--) {
for (int numberB = 999; numberB >= numberA; numberB--) {
int product = numberB * numberA;
if (isNumberPalindrome(product) && largestPalindromicProduct < product) {
largestPalindromicProduct = product;
}
}
}
return largestPalindromicProduct;
}
Complexity
In above naive solution we basically made all the possible pairs from to . All pairs can be made in time, hence is the complexity.
Elegant Approach
As I mentioned in the theory and concept section that, all palindromic numbers of even length are divisible by . Lets see why and what we can deduce from it.
Lets say our number is (since its a six digit number).
So form above we can say that one of the digit number is at least a multiple of . And we also know, are single digits varying from , rest is just looping for these three variables.
Code
/**
* A function to find largest palindrome product below a given certain number
*
* @param num
* : limit unders which we need to find our product
* @return largest palindromic number which can be written as product of two 3
* digit numbers
*/
public static int largestPalindromeProduct(int num) {
int largestPalindromicProduct = -1;
for (int a = 9; a >= 1; a--) {
for (int b = 9; b >= 0; b--) {
for (int c = 9; c >= 0; c--) {
int subProduct = 9091 * a + 910 * b + 100 * c;
for (int divider = 90; divider >= 10; divider--) {
if ((subProduct % divider) == 0 && (subProduct / divider) < 999 && subProduct * 11 < num) {
largestPalindromicProduct = subProduct * 11;
return largestPalindromicProduct;
}
}
}
}
}
return largestPalindromicProduct;
}
Complexity
I will say its being a constant. Since we will always be doing a constant work which is not dependent on any input number.
Brilliant solution
While browsing how other people solved the problem on Projecteuler website I came across a masterpiece. A solution without pen and paper. Its a solution given by (not my solution).
You can also do this with pen and paper.
You have a number: (100a + 10b + c)(100d + 10e + f) which is a palindrome.
This factors out to: 100cd + 10ce + cf + 1000bd + 100be + 10bf + 10000ad + 1000ae + 100af
Assuming the first digit is 9, then cf must be equal to nine. Also, both a and d must then be equal to nine. The only ways to make the last digit of the product of two integers 9 would be if those integers were either of:
1 and 9
3 and 3
7 and 7
So, both numbers must start with 9, end with either 1, 3, 7, or 9, and one of them must be divisible by 11. The only numbers divisible by 11 from 900 - 1000 are:
902
913
924
935
946
957
968
979
990
You can discard all of those that do not end in either 1, 3, 7, or 9, and you are left with:
913
957
979
So now the presumed answer is either:
(900 + 10 + 3)(900 + 10x + 3)
(900 + 50 + 7)(900 + 10x + 7)
(900 + 70 + 9)(900 + 10x + 1)
Factoring all those out, you get:
810000 + 9000x + 2700 + 9000 + 100x + 30 + 2700 + 30x + 9 824439 + 9130x
Now, for the first digit 824439 + 9130x to be 9, x must be 9 (if x were 8, then 824439 + 9130x = 897479, and the first digit is 8). And so you have 913 * 993, which is the answer. You can factor the others out to see if they produce a bigger answer, which they don’t.
Test Your Skills
Wanna try a harder version of the above problem ? Check this HackerRank problem.
Solution
The solution will remain same as above method , you just need to call it for each test case.
Leave a Comment
Your email address will not be published. Required fields are marked *