Problem 4:
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.
99.Find the largest palindrome made from the product of two 3-digit numbers.
--
This problem is also simple enough to be solved using an intuitive brute force method. A solution can be found by completing three easy steps.
Step 1: Compute all the products of three-digit numbers.
Step 2: Examine each of these products and remove those that are not palindromes.
Step 3: Find the biggest number of the remaining products.
Note: There are probably much faster ways of solving this problem, but at this point we don't really need to worry about optimization. This is a quick solution that gets us the correct answer without having to spend too much time planning or programming.
Now that we have broken the program down into three steps, let's look at how these steps can be put into a Java program.
Step 1: We'll use two simple loops to generate these products. We use two variables, and call them "number1" and "number2". Each number starts at the largest three-digit number (999) and loops down to the smallest three-digit number (100). On each time through the outer loop we have an inner loop that decrements number2 until it reaches 100. We keep number1 at 999 until we have multiplied it by every three-digit number and then we decrement it to 998. We then reset number2 to equal the current value of number1 and go through the inner loop again. In this way, we multiply every three-digit number by every other three-digit number.
Step 2: This step actually happens in the midst of the loop used for Step 1 in the code, but it is easiest to think of them as two different steps. This step simply checks if the current product is a palindrome. I have abstracted this step into a method called "checkForPalindrome." It basically starts at the outside numbers (first and last) and checks that they are the same. It them moves one digit towards the middle of the number and checks that they are again the same. As soon as it reaches the middle it's done. If all the checks have been equal, then it is a palindrome. If any of the checks have not been equal, then it is not a palindrome.
Step 3: This step is actually very easy in our program. Programmers often want to sort collections of numbers and find the largest one, which is exactly what we want to do. Fortunately for us, the Java language has a library function to sort a collection. We simply call this sort function and then get the first item in the collection since it is now the largest number in the collection. We then print out this number since it is the correct answer.
Again, take a look at the source code even if this doesn't all make sense. In many ways, it's easier to understand something by reading the code than it is to understand it by reading an English explanation. Feel free to ask any questions in the comments!
Source code:
/**
* 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.
*
* Answer: "906609"
*/
package problem_004;
import java.util.ArrayList;
import java.util.Collections;
public class Problem_004_Solver
{
public static void main(String[] args)
{
ArrayList<Integer> answers =
new ArrayList<Integer>();
int number1 = 999;
int number2 = 999;
int product = 0;
while(number1>100)
{
product = number1*number2;
if(checkForPalindrome(product))
{
answers.add(product);
}
if(number2==100)
{
number1--;
number2 = number1;
}
else
{
number2--;
}
}
Collections.sort(answers);
for(int i=0; i<answers.size(); i++)
{
System.out.println(answers.get(i));
}
}
/**
* Checks if the provided number is a palindrome.
* A number is a palindrome if it reads the same
* forwards and backwards. Example: 101
*
* @param number - The number to be checked for
* palindromic characteristics.
* @return - True if the number is a palindrome,
* false if it is not.
*/
public static boolean checkForPalindrome(int number)
{
String numString = ""+number;
boolean retVal = true;
int firstIndex = 0;
int secondIndex = numString.length()-1;
while(firstIndex<secondIndex)
{
if(numString.charAt(firstIndex)!=
numString.charAt(secondIndex))
{
retVal = false;
break;
}
firstIndex++;
secondIndex--;
}
return retVal;
}
}
