Project Euler #4 – Largest Palindrome Product

Problem Overview

• A palindromic number reads the same forward and backward (e.g. 121, 9009).


• Goal: Find the largest palindrome made from the product of two 3-digit numbers.


• Example:
  • 91 × 99 = 9009 is a palindrome.
  • For the full problem, we must search all products from 100 to 999.

C Solution

#include <stdint.h>
#include <stdio.h>
#include <stdbool.h>

bool isPalindrome(uint64_t n)
{
    if (n <= 9)
    {
        return true;
    }

    uint64_t original = n;
    uint64_t reversed = 0;

    while (n)
    {
        reversed *= 10;
        reversed += n % 10;
        n /= 10;
    }

    return original == reversed;
}

uint64_t solve()
{
    uint64_t largestProduct = 0;

    for (uint64_t i = 999; i >= 100; i--)
    {
        for (uint64_t j = i; j >= 100; j--)
        {
            const uint64_t product = i * j;
            if (isPalindrome(product) && product > largestProduct)
            {
                largestProduct = product;
            }
        }
    }

    return largestProduct;
}

int main()
{
    fprintf(stdout,
            "Largest palindrome made from the product of two 3-digit numbers is %lu\n",
            solve());
    return 0;
}

1. Checking if a Number Is a Palindrome


• The helper function isPalindrome reverses the decimal digits of n and compares:

bool isPalindrome(uint64_t n)
{
    if (n <= 9)
    {
        return true;
    }

    uint64_t original = n;
    uint64_t reversed = 0;

    while (n)
    {
        reversed *= 10;
        reversed += n % 10;
        n /= 10;
    }

    return original == reversed;
}

• Single-digit numbers are trivially palindromes.
• In the loop:
  • Take the last digit n % 10 and append it to reversed.
  • Drop the last digit with n /= 10.
• At the end, if original == reversed, the number is palindromic.



2. Searching Over 3-Digit Products



uint64_t solve()
{
    uint64_t largestProduct = 0;

    for (uint64_t i = 999; i >= 100; i--)
    {
        for (uint64_t j = i; j >= 100; j--)
        {
            const uint64_t product = i * j;
            if (isPalindrome(product) && product > largestProduct)
            {
                largestProduct = product;
            }
        }
    }

    return largestProduct;
}

• We iterate downwards from 999 to 100:
  • Outer loop: i runs from 999 down to 100.
  • Inner loop: j starts at i and goes down to 100.
  • Using j = i avoids checking both i × j and j × i separately.


• For each pair (i, j):
  • Compute product = i * j.
  • If it is a palindrome and larger than the current largestProduct, update the maximum.


• After exploring all pairs, largestProduct holds the answer.



3. main and Output



int main()
{
    fprintf(stdout,
            "Largest palindrome made from the product of two 3-digit numbers is %lu\n",
            solve());
    return 0;
}

• solve() returns the largest palindromic product, which is then printed to standard output.
• Return value 0 signals successful program termination.



4. Complexity and Notes


• There are at most about (999 - 99)^2 ≈ 810,000 pairs to test.
• For each pair, isPalindrome runs in time proportional to the number of digits (at most 6 digits here).
• Overall this is easily fast enough in C for a one-off calculation.
• Further micro-optimizations (like breaking early if the product cannot exceed the current maximum) are possible, but unnecessary for this problem size.