Project Euler #4 - C

Question:

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.

Solution:

So, a there are two basic facts about this problem to keep in mind. One, any two 3-digit numbers will have a 6 digit product. Second, a 6-digit palindrome will be in the form ijkkji, where j and k are integers from 0-9 and i is an integer from 1-9. We know that i cannot be zero because of the fact that the product must be a 6-digit number. If i were 0, the product would only contain 5 digits (ie: leading zeroes do not count). 


So with this in mind, this problem is simple. Since we are looking for the largest palindrome with two 3-digit products, begin at 999999 and check whether this number is the product of two 3 digit numbers. If it is not, we must decrement our palindrome from the inside out. In other words, our loop is structured as i -> j -> k. We decrement k, then j, then i as we loop through our possible palindromes. 


Lets put these ideas in concrete with some code. 



#include <stdio.h>
#define MIN3 100
#define MAX3 999


int main (void)
{
int i, j, k, m;
int subj; 


for (i = 9; i > 0; i--)
{
for (j = 9; j >= 0; j--)
{
for (k = 9; k >= 0; k--)
{
subj = k*1100 + j*10010 + i*100001; // create our test subject


for (m = MAX3; m >= MIN3 ; m--)
{
if (subj % m) // if the number is not divisible go to the next value of m
continue;

int div = subj / m; 
if (div >= 100 && div <= 999) // we found our subject!
{
printf("Largest palindrome with 3 digit multipliers is %d", subj);
return 1;
}
}
}
}
}
return 0;
}


Compile and watch the solution appear before your eyes!