Problem 4

Posted on Apr 26, 2023

Problem

Find the largest palindrome which is the product of two 3-digit numbers.

General 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.

Solution: Go

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)
}

Solution: PHP

PHP has a strrev function so the is_palindrome function is simpler.

<?php

declare(strict_types=1);
error_reporting(E_ALL);

function is_palindrome(int $number) : bool
{
    // A number is a palindrome if its string representation
    // is the same when reversed
    $str = strval($number);
    return ($str === strrev($str));
}

$longest_palindrome = 0;

for ($i = 100; $i <= 999; $i++)
{
    for ($j = 100; $j <= 999; $j++)
    {
        $product = $i * $j;

        if (is_palindrome($product) && $product > $longest_palindrome)
        {
            $longest_palindrome = $product;
        }
    }
}

print("$longest_palindrome\n");

Solution: C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <inttypes.h>

int main(void)
{
  uint32_t largest_palindrome = 0;

  for (uint16_t alpha = 999; alpha >= 100; alpha--)
  {
    for (uint16_t beta = 999; beta >= 100; beta--)
    {
      uint32_t product = alpha * beta;
      uint8_t digit_count = product < 100000 ? 5 : 6;
      uint8_t buffer_size = digit_count + 1; // Plus one for the terminating NUL character
      char buffer[buffer_size];

      printf("Checking to see if %" PRIu32 " is a palindrome\n", product);

      // Assume palindrome until proved otherwise
      bool is_palindrome = true;

      int output_length = snprintf(buffer, buffer_size, "%" PRIu32, product);

      if (output_length >= buffer_size)
      {
        fprintf(stderr, "Output length (%" PRIu8 ") is greater than or equal to buffer size (%" PRIu8 ")\n", output_length, buffer_size);
        return EXIT_FAILURE;
      }

      // Check each pair of digits until we cross over (start_digit <= end_digit)
      for (uint8_t start_digit = 0, end_digit = digit_count - 1; start_digit <= end_digit && is_palindrome; start_digit++, end_digit--)
      {
        printf("Comparing %c with %c\n", buffer[start_digit], buffer[end_digit]);
        if (buffer[start_digit] != buffer[end_digit])
        {
          is_palindrome = false;
        }
      }

      if (is_palindrome)
      {
        if (product > largest_palindrome)
        {
          largest_palindrome = product;
        }
      }
    }
  }

  printf("Largest palindrome is: %" PRIu32 "\n", largest_palindrome);

  return EXIT_SUCCESS;
}