OK. Here it is, problem number 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."*

First, we need a function to check if a String is palindrom. Here is the code:

` 1 `**def** isPalindrome**(**s: **String****)** **=** **{**
2 **val** incr **=** s.length **%** 2
3 s.substring**(**0, s.length**/**2**)** **=****=**
4 s.substring**(**incr **+** s.length**/**2**)**.reverse
5 **}**

Note the use of incr that has value either 0 or 1. It is intended to handle the case where the length of the string is odd.Then, a little analysis.The product of two 3-digit numbers has 5 or 6 digits.Assume that we will find the largets palindrome as 6 digit number.. The number then will be in the form of 'abccba' with the following property:The largest palindrom=100000 a + 10000 b + 1000 c + 100 c + 10 b + a= 10 0001 a + 10010 b + 1100 cwhich is a multiply of 11. So, one of the 3 digit number will then multiply of 11. This information can be used to reudce the brute force nature of the search.The largest multiply of 11 is 11 * 90 = 990.The search then starts from 990, followed by 979, and subsequent mutliply 11 until 11 * 9 that is no longer 3 digit number. The multiply 11 number is then multiplied by all 3 digit numbers.To optimize further, we take advantage of the iteration nature that goes down from the largest multiply 11 until 99. If we have a maximum number xi* y, the product of xii < xi with z can only be larger than xi * y if z > y. This allows us to stop earlier. The code is the following. Note the annotation tailrec that asks the compiler to check if the method is tail recursive.`1 @tailrec 2`

defgetLargestPalindrome(3 x :Int, y :Int, 4 max:Int, xMax:Int, yMax:Int):Int={5if(x*11<100){6 max 7}else{8valmul=x*11*y 9 10if(mul>max){11if(isPalindrome(mul.toString))12 getLargestPalindrome(x-1, 999, mul, x, y)13else14 getLargestPalindrome(x, y-1, max, xMax, yMax)15}16else{17 getLargestPalindrome(x-1, 999, max, xMax, yMax)18}19}20}When executed, the largest palindrom is indeed 6 digits, so the algorithms above are applied. What's xMax and yMax for ? It's the two 3 digit numbers.

## No comments:

Post a Comment