Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 30 minutes | Coding time: 5 minutes
In this problem, we will find the largest palindrome that is a product of two three-digit numbers. In brute force, there are 810000 comparisons which we have reduced to 362 comparisons based on three deep insights. This is a dramatic improvement.
A palindrome is a number where the order of digits is same where it is read from front or back. Example: 104401, 9023209 and so on.
For example: 111111 is a palindrome and is a product of 777 and 143. Similarly, we need to find the largest such palindrome.
In short, the insights are:
- If the two numbers are N1 and N2, then either of them should be divisible by 11
- In brute force, we should start with higher values of N1 and N2 that top to bottom
- We need to check only for N2 < N1 to avoid duplicate checking.
We will follow a complete flow to understand the insights deeply.
Let us begin with the most basic approach where we will generate all pairs of three digit numbers and check if the resulting number is a palindrome. From all palindromes, we will keep the largest palindrome.
We can check whether a number is a palindrome or not by creating a reverse of the number by using modulus and multiplication operations.
Pseudocode to check palindrome:
palindrome(int N)
{
int temp = 0, backup = N;
while(N > 0)
{
temp = temp * 10 + N%10;
N = floor(N/10);
}
if (temp == backup)
return true
else
return false
}
With the above utility, the brute force approach of getting the largest palindrome is:
for i from 100 to 999
for j from 100 to 999
int N = i * j
if(palindrome(N) and N > largest)
largest = N
return N
Note there are 899 * 899 = 808201 possibilities to check.
Implementation of the above technique in Java:
import java.util.*;
class opengenus
{
static boolean palindrome(int N)
{
int temp = 0, backup = N;
while(N > 0)
{
temp = temp * 10 + N%10;
N = (int)Math.floor(N / 10);
}
if(temp == backup)
return true;
return false;
}
static int largest_palindrome()
{
int largest = 0;
for(int i = 100; i <= 999; i++)
{
for(int j=100; j<=999; j++)
{
int N = i * j;
if(palindrome(N) and N > largest)
largest = N;
}
}
return largest;
}
public static void main (String[] args)
{
int answer = largest_palindrome();
System.out.println(answer);
}
}
Output:
906609
The number of computations in this case is 810000. We will reduce this dramatically.
Optimization 1
Our first optimization is to start the loop from 999 to 100 instead of 100 to 999. This is because our objective is to find the largest number and if we start from largest three-digit numbers, we may expect to reach the result faster.
In this optimization, it is not clear how many cases are skipped as we do not know the result as of now.
Having a knowledge of the answer, we know that we will arrive at the answer as soon as 993 x 913.
The pseudocode for this technique will be:
for i from 999 to 100
for j from 999 to 100
int N = i * j
if(palindrome(N) and N > largest)
return N
Note that as soon as we get a palindrome, we are returning it in this case as all further palindromes will be smaller as we will be using smaller sub parts.
Implementation of this technique in Java:
import java.util.*;
class opengenus
{
static boolean palindrome(int N)
{
int temp = 0, backup = N;
while(N > 0)
{
temp = temp * 10 + N%10;
N = (int)Math.floor(N / 10);
}
if(temp == backup)
return true;
return false;
}
static int largest_palindrome()
{
int largest = 0;
for(int i = 999; i >= 100; i--)
{
for(int j=999; j >= 100; j--)
{
int N = i * j;
if(palindrome(N) and N > largest)
return N;
}
}
return 0;
}
public static void main (String[] args)
{
int answer = largest_palindrome();
System.out.println(answer);
}
}
Output:
580085
This optimization reduces the number of comparisons or computations to 4017 which is a significant improvement. We can improve it further.
Optimization 2
The idea in this is to avoid duplicate checks. Due to our loop, we are check N1 * N2 and N2 * N1 twice even though the result is same.
To avoid this, we shall begin the second loop from the integer of the first loop. This will reduce the number of comparisions by half overall.
Pseudocode:
for i from 999 to 100
for j from i to 100
int N = i * j
if(palindrome(N))
return N
Implementation:
import java.util.*;
class opengenus
{
static boolean palindrome(int N)
{
int temp = 0, backup = N;
while(N > 0)
{
temp = temp * 10 + N%10;
N = (int)Math.floor(N / 10);
}
if(temp == backup)
return true;
return false;
}
static int largest_palindrome()
{
int largest = 0;
for(int i = 999; i >= 100; i--)
{
for(int j=i; j >= 100; j--)
{
int N = i * j;
if(palindrome(N))
return N;
}
}
return 0;
}
public static void main (String[] args)
{
int answer = largest_palindrome();
System.out.println(answer);
}
}
Output:
580085
The number of comparisons/ computations in this case is 4007.
Optimization 3
This is the major and most insightful optimization.
Our answer (largest palindrome) should have atleast 6 digits as we are multiplying 2 three digit numbers. Let us assume that our answer A has 6 digits and is a palindrome. In this case, it will have 3 unique digits say X, Y and Z.
A = 100000 * X + 10000 * Y + 1000 * Z + 100 * Z + 10 * Y + X
We can simplify this as:
A = 100001 * X + 10010 * Y + 1100 * Z
A = 11 * (9091 * X + 910 * Y + 100 * Z)
Hence, if our answer is 6 digit, it should be a multiple of 11. As 11 is a prime number, either of the two numbers being multiplied should be a multiple of 11.
We must note that our answer must be 6 digit number as both 100 x 100 and 999 x 999 are 6 digit numbers and all other products come in between.
For this, if the outer loop number is not a multiple of 11, then the inner loop must be a multiple of 11 and hence, we can skip several possibilities.
The pseudocode for this technique is:
for i from 999 to 100
if i % 11 == 0
step = 1
else
step = 11
for j from i + 11 - i%11 to 100 in increment of step
int N = i * j
if(palindrome(N))
return N
Note that i + 11 - i%11 is the number just greater than i which is a multiple of 11.
Implementation:
import java.util.*;
class opengenus
{
static boolean palindrome(int N)
{
int temp = 0, backup = N;
while(N > 0)
{
temp = temp * 10 + N%10;
N = (int)Math.floor(N / 10);
}
if(temp == backup)
return true;
return false;
}
static int largest_palindrome()
{
int largest = 0, step = 1;
for(int i = 999; i >= 100; i--)
{
int j = 0;
if(i % 11 == 0)
{
step = 1;
j = i;
}
else
{
step = 11;
j = i - i % 11;
}
for(; j >= 100; j = j - step)
{
int N = i * j;
if(palindrome(N))
{
return N;
}
}
}
return 0;
}
public static void main (String[] args)
{
int answer = largest_palindrome();
System.out.println(answer);
}
}
Output:
580085
The number of comparisons in this case is 362 which is dramatically reduced from the initial value.
Thus, we have greatly optimized this problem. You are, now, a master of this technique. Enjoy.
