Disclaimer: I will NOT disclose what the answers are to these problems. The intent is that the testing is just as important, and in most cases, more than the answer. If you want to know what the answer is without solving the problem, a simple google search will tell you what it is.
Background:
- If you are not familiar with the series, please read this.
- This is Java driven as well as JUnit 4.
- You are familiar with TDD tenants.
References:
“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.”
Difficulty: Easy
The Test File:
- Please download it here.
Explanation:
A brute force approach would be to go from 10,000 to 998,001 and evaluating each number for the two criterea:
- Is this number a Palindrome?
- Is this number a product of two three digit numbers?
Not being a mathematician, I kind of liked a brute force idea, but I tweaked it a bit. Instead of an incremental approach from min to max, I decided to use a decremental approach. I suspected that the answer should be in the 900,000′s. I only have to traverse through, at most, 100,000 integers.
For determining the divisibility, I was also going to take a brute force approach as well, but I was going to make an assumption. That is, I’m going to guess that both products will be between 800-999. So the determination will be a decremental loop starting from 999. If the palindrome is evenly divisible by that number, I would divide the palindrome with that number, and check if the product is less than 1000. So it goes like this:
- Start from 998,001 and decrement by one in a loop.
- Is the number a palindrome?
- If so, is it divisible by a number in a decremental range starting from 999, and ending in 800.
- If so, is the product of the palindrome and that number less than 1000?
- Good. Print the number, or print the number and exit.
The hardest thing about this problem then was then evaluating whether or not a given number is a palindrome or not. I know what a palindrome is, but I never implemented an algorithm that evaluated a palindrome. With strings, it’s slightly easier because you can easily compare first and last characters in Java and then strip them. You have charAt at your disposal, substring and many implementations of strip (first and last chars).
With numbers how do you do that? I didn’t know, so I had to write it out on paper. After that, it was fairly straight forward. I had to write an algorithm that compared the first and last digits of the number using modulo based on ten and divisors based on 10. Then I had to write an extractor that stripped out the left and right most digits.
Stop if the stripped digit is either single or double digits. If it gets down to single digits, the number is a palindrome. i.e.: 151 is a palindrome because the first and last digits are equal and the remainder is 5. This works for all three digit (or odd) digit numbers.
Stop if the stripped remainder is two digits. If the number is a palindrome (22, 33, etc) return true. Else return false.
Implementation Details:
Methods shouldTestGetLeftMostNumber, and shouldTestGetRightMostNumber were my first two test methods. It was easy to implement (10 based divisors retrieved left most numbers, modulo retrieved right most numbers). I started with one test first, for example:
- Given the number 5, I expect that left most number is 5. Assert that 5 is expected against the actual, 5.
Then the tests followed…
- Given the number 61, I expect that the left most number is 6. Assert that expected and actual are equal.
- You can do tests for any random 3, 4, 5 and 6 digit numbers.
Getting the right most number was similar and just as trivial. Example:
- Given a number 462, I expect that the right most number is 2. Assert!
- I didn’t do negative cases because I used random numbers.
So a palindrome checker is fun to implement.
- Are the two numbers on the ends equal? If not, stop and return false;
- If so return the center.
- Stop and return true if the remainder is single digit.
- Stop and return false if the remainder is double digit but not a palindrome.
- Stop and return true if the remainder is double digit and is a palindrome (22, 33, 44, etc).
That’s it!!! Now, how you implement your methods are totally up to you. You can use recursion for the palindrome checker, but I didn’t. I used iterative approaches for speed (although, unlike the Fibonacci problem, recursion shouldn’t pose to much of a performance hit).
Divisibility by three digits is easy as well. It’s trivial so I need not write out the implementation. Just guess that the range is between 999-800, decremented.
