Find the largest palindrome which is the product of two 3-digit numbers.
Solution
There are 900 three digit numbers (100-999), so to find the product of all the possible combinations we would need 900 * 900 = 810,000 multiplications. This is trivial on a modern processor and therefore we can brute force a solution without needing to optimise, although the question of whether we could reduce the search space beforehand remains open.
A simple way to check whether a number is a palindrome is to convert it to a string and reverse it. If the original and reversal are the same, the number is a palindrome.
Unfortunately Go does not have a built-in function to reverse a string (or a slice, if we converted a string to a slice of single-character strings). This means we have to compare each digit of the string from either end instead. The isPalindrome function does this.
package main
import (
"fmt"
"strconv"
)
func isPalindrome(n int) bool {
isPalindrome := true
str := strconv.Itoa(n)
for startDigit, endDigit := 0, len(str)-1; startDigit <= endDigit && isPalindrome; startDigit, endDigit = startDigit+1, endDigit-1 {
if str[startDigit] != str[endDigit] {
isPalindrome = false
}
}
return isPalindrome
}
func main() {
longestPalindrome := 0
for i := 100; i <= 999; i++ {
for j := 100; j <= 999; j++ {
product := i * j
if product > longestPalindrome && isPalindrome(product) {
longestPalindrome = product
}
}
}
fmt.Println(longestPalindrome)
}