04: Lagest palindrome product

Problem statement

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.

Thoughts

I thought for a while about whether I could find a solution that didn't involve iteration, but concluded that I couldn't think of one. I tried looking at the prime decomposition of palindromic numbers, which seemed promising at first, but ended up being a coincidence.

All palindromic numbers between 10 and 100 are multiples of 11, itself a palindromic prime. A lot of palindromes between 100 and 200 are either primes # themselves or products of palindromic primes, but it begins to fall down the higher you go.

Solution

In conclusion, I think this needs to be solved iteratively. We don't need to count up from 0, we can just count down from 999x999. After each iteration, check if the number is palindromic. Break if we find a palindrome, or if the product is lower than the largest palindrome we've already found.

I'm sure this could be optimised with some way to break when the product is guaranteed to be too low (i.e. there's no way 100x100 is going to be higher than 900x900), but I haven't bothered with that.

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

bool isPalindrome(int num)
{
	int numLen = floor(log10(num)) + 1;
	int rev = 0;
	int revLen = 0;

	while (revLen < (numLen / 2)) {
		rev = (rev * 10) + (num % 10);
		num = num / 10;
		revLen++;
	}
	if (numLen % 2 == 1) {
		num = num / 10;
	}
	return rev == num;
}

int main()
{
	int largest = -1;
	for (int i = 999; i > 100; i--) {
		for (int j = 999; j > 100; j--) {
			int product = i * j;
			if (product <= largest) {
				break;
			}

			if (isPalindrome(product)) {
				largest = product;
				break;
			}
		}
	}

	printf("%d", largest);
}