oschvr

a blog about software, programming, business, travelling and life.

← Problems

Largest palindrome product

24 days ago

 02/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.

1
2
3
4
5
6
7
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):

1
2
3
4
5
6
forLoop (if n>0, n = ( 12345 % 10 ) ) (
  reversed = (10 * 0) + 12345 % 10
  reversed = (0) + (5)
  reversed = 5
)
n = 1234

At the second iteration:

1
2
3
4
5
6
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

1
2
3
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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

Answer

Largest Palindrome: 906609