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;

        }

}

Advertisements