oschvr

a blog about software, cloud computing, security, money, business, travelling and life.

← Problems

Largest palindrome product

1 min  

over 1 year ago

 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

Answer: Largest Palindrome: 906609