Wednesday, July 1, 2009

Grind Report 6

Getting back on track.

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;
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)
//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