Will Clausen's Website

Categories
WCW

Solution: Project Euler Problem 4

The Problem:

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.

My solution (in C++):


// Author: Will Clausen
//
// Date: Jan 7, 2013
//
// This program will solve Problem 4 of Project
// Euler

// INCLUDES

#include <cstddef>
#include <cmath>
#include <set>
#include <iostream>
#include <sstream> // For converting numbers to strings.

using namespace std;

// DECLARATIONS (could be put in a header, but there's only 2
// so I'll spare myself the trouble).

size_t problem4(size_t numDigits);
bool isPalindrome(size_t Num);

// IMPLEMENTATIONS

// This function will return the largest palindromic number that is the product
// of two numbers with numDigits digits.
size_t problem4(size_t numDigits)
{
	size_t startingNum = pow(10, numDigits-1);
	size_t endingNum = pow(10, numDigits);
	size_t nextNum;
	size_t largestPalindrome = startingNum;

	// Generate all palindromes and add them to a set.
	for (size_t x = startingNum; x < endingNum; ++x) {
		for (size_t y = startingNum; y < endingNum; ++y) {
			nextNum = x*y;
			if (isPalindrome(nextNum)) {
				if (nextNum > largestPalindrome) {
					largestPalindrome = nextNum;
				}
			}
		}
	}

	return largestPalindrome;
}

// Helper function to determine if a number is a palindromic number
bool isPalindrome(size_t Num) {
	// Convert the number to a string
	string Number;
	stringstream convert;
	convert << Num;
	Number = convert.str();
	size_t NumLen = Number.length();

	// Check the string
	for (size_t i = 0; i < NumLen/2; ++i) {
		if (Number[i] != Number[NumLen - 1 - i])
			return false;
	}

	return true;
}

// Solution: 906609

Comment if you know a way to think about this problem that leads to a faster solution. In particular, I wonder if there’s a faster way to generate possible numbers than brute-force search.

Leave a Reply

Your email address will not be published.