← Problems

# Largest palindrome product

#### over 1 yearago

###### 03/05/2019

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

The first observation is that the number should be in the range of 10000 and 998001. There's a couple aproaches to the problem, such as:

• Multiplicating two 3-digit numbers and checking the result if its a palindrome
• Creating palindromes and getting the factors to see if that pair is what we're looking for.

I'll go for the first approach. First I'll create an int reversal function to call whenever I want to check if a number is a palindrome.

func reversed(n int) int
{
reversed := 0
for ; n > 0; n = n / 10 {
reversed = 10 * reversed + n % 10
}
return reversed
}

Let me explain what this function does in 3 steps:

1. Isolate the last digit number from the input number(n)
2. Append the last digit to a new variable (reversed)
3. Remove the last digit from the input number (n)

Consider 12345 as n

At the first iteration (pseudocode):

forLoop (if n>0,
n = ( 12345 % 10 ) ) (
reversed = (10 * 0) + 12345 % 10
reversed = (0) + (5)

reversed = 5
)
n = 1234

At the second iteration:

forLoop (if
n > 0, n = ( 1234 % 10 ) ) (
reversed = (10 * 5) + 1234 % 10
reversed = (5)
+ (4)
reversed = 54
)
n = 123

And so on... Here is an detailed explanation of this reversing algorithm.

Next I'll create a helper function to return true/false

func
isPalindrome(n int) bool{
return n === reversed(n)
}

Lastly, we'll multiply a · b to check if a result isPalindrome and iterate to find the largest palindrome.

func
main(){
largestPalin := 0
a := 0
for ; a <= 999; < a++ {
b := 100

for ; b <= 999; b++{
c := a*b
if isPalindrome(c) && c > largestPalindrome{

largestPalindrome = c
}
}
}
fmt.Println(largestPalindrome)
}

Here's the code

package main

import (
"fmt"
"time"
)

func main()
{
start := time.Now()
largestPalin := 0
a := 0
for ; a <= 999; a++ {
b
:= 100
for ; b <= 999; b++ {
c := a * b
if isPalindrome(c) &&
c > largestPalin {
largestPalin = c
}
}
}
fmt.Println("Execution time: ", time.Since(start))
fmt.Println("Largest Palindrome: ", largestPalin)
}

func
reversed(n int) int { // 456789
reversed := 0 // 0
for ; n > 0; n = n / 10
{
reversed = 10*reversed + n%10
}
return reversed
}

func isPalindrome(n
int) bool {
return n == reversed(n)
}


Execution time: 13.226084ms