Problem 4

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.

*WARNING: This contains the solution!*

This was pretty easy. My immediate thoughts on this was to use brute force (specifically 2 for loops starting from 999 and going down to 100). Fighting against brute force, I attempted to see if there was a better way to go about solving this. I tried a few things but the only thing I came up with was something about the number 11.

So I went onto brute force and here is what I came up with.

#include <iostream>

#include <string>

#include <sstream>

using namespace std;

bool isPalindrom(int number)

{

//convert the number to a string

std::string s;

std::stringstream out;

out << number;

s = out.str();

bool isPal = true;

//compare the first and last elements and check to see if they are equal

//continue moving in until either a match is not found or no more elements to compare

//always skips the middle since it will always match itself

for (int i = 0; i < (s.length() / 2); ++i)

{

if (s[i] != s[s.length() - i - 1])

{

isPal = false;

break;

}

}

return isPal;

}

int main()

{

int answer = 0;

int product;

for (int i = 999; i > 100; --i)

{

for (int j = 999; j > i; --j)

{

product = i * j;

//return if the product is less than the answer.

//this means it cannot get any better

if (answer > product)

break;

//check to see if the product is a palindrom

if (isPalindrom(product))

answer = product;

}

}

cout << "Answer: " << answer << endl;

}

*saved game*

## No comments:

## Post a Comment