The problem was to find the largest palindrome made from the product of two 3-digit numbers.
I did not want to do a brute force thing. So I searched the net for some property of palindrome which might help me in the solution. But I found none. However I stumbled across a piece of information which helped reduce the number of computations in the brute force. The piece of information was this:
836 * 836 = 698896
So all I did was to count up from 836 to 999. Below is the code that I wrote in Java:
public class Problem_4 {
private static int knownPalin = 698896;
private boolean checkPalindrome(String word) {
StringBuffer reverse = new StringBuffer(word);
reverse.reverse();
return word.equals(reverse.toString());
}
public void findGreatestMultiplePalindrome() {
int palin = Problem_4.knownPalin;
int a = 836;
int b = 836;
Stopwatch stopwatch = new Stopwatch();
stopwatch.start();
for (int i = 836; i < 1000; i++) {
int j = palin / i;
for (; j < 1000; j++) {
int prod = i * j;
if (checkPalindrome(String.valueOf(prod))) {
palin = prod;
a = i;
b = j;
}
}
}
stopwatch.stop();
System.out.println("The reading for operation is: " + stopwatch);
System.out.println("A: " + a + ", B: " + b + ", Product: " + palin);
}
public void findGreatestMultiplePalindromeAlternate() {
int palin = Integer.MIN_VALUE;
int a = 0;
int b = 0;
Stopwatch stopwatch = new Stopwatch();
stopwatch.start();
for (int i = 999; i > 99; i--)
for (int j = 990; j > 99; j -= 11) {
int prod = i * j;
if (prod > palin && checkPalindrome(String.valueOf(prod))) {
palin = prod;
a = i;
b = j;
}
}
stopwatch.stop();
System.out.println("The reading for operation is: " + stopwatch);
System.out.println("A: " + a + ", B: " + b + ", Product: " + palin);
}
public static void main(String[] args) {
Problem_4 p = new Problem_4();
p.findGreatestMultiplePalindrome();
}
}
It took 15ms to output the answer.
Then I looked at the solutions proposed by the others. Most of the people had used brute force. However, there was one smart simplification done.
Any palindrome is of the form abccba.
abccba = 100000a + 10000b + 1000c + 100c + 10b + a = 100001a + 10010b + 110c
Thus our palindrome is of the form
11(9091a + 910b + 100c ) = mn
And since 11 is a prime number, one of our m or n has to be a multiple of 11. Thus instead of looping through all the numbers, having one loop only through the multiples of 11 reduces the number of products to be checked.
The alternate method is the one with the multiple of 11 idea.
Popularity: 27% [?]
Related posts: