## Problem 4: Largest palindrome product

*Difficulty: Easy

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.

How to solve:

For the shake of simplicity, I come up with an O(n^2) solution, check all possible solutions from 101 to 999 (inclusive)

Solution took about 55 to 120 ms

Implementation (Java):

public class Prob4 {

public static void main(String[] args) {

long cur = System.currentTimeMillis();

int max = Integer.MIN_VALUE;

for(int count1 = 100; count1 <= 998; ++count1) {

for(int count2 = count1+1; count2 <= 999; ++count2) {

if(isPalindrome(String.valueOf(count1*count2)) && count1*count2 >                                   max) {

max= count1*count2;

}

}

}

System.out.println(max);

System.out.println(“Took “ + (System.currentTimeMillis() cur) + ” ms”);

}

private static boolean isPalindrome(String s) {

int length = s.length();

for(int count = 0; count < length/2; ++count) {

if(s.charAt(count) != s.charAt(length1count))

returnfalse;

}

return true;

}

}