Saturday, April 28, 2012

Project Euler, Problem 4 solution

(http://projecteuler.net/problem=4)
"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."


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

bool is_palindrome(unsigned int const num) {
    unsigned int res = 0;
    unsigned int n = num;
    while(n > res) {
        res = res*10 + n%10;
        n /= 10;
    }
    return n == res;
}

int main() {
    int i, j, c = 0;
    unsigned int res = 0;
    /*
    The palindrome can be written as:
        abccba
    Which then simpifies to:
        100000a + 10000b + 1000c + 100c + 10b + a 
    And then:
        100001a + 10010b + 1100c
    Factoring out 11, you get:
        11(9091a + 910b + 100c)
    So the palindrome must be divisible by 11.
    Seeing as 11 is prime, at least one of the numbers 
    must be divisible by 11.
    So brute force only with less numbers to be checked:
    lets iterate only through the highest 100
    */
    for(i = 999; i > 899; --i) {
        for(j = 999; j > 899; --j) {
            res = i*j;
            ++c;
            if(is_palindrome(res)) {
                printf("\nThe largest palindrome is %d \
                    \nIs product of %d and %d \
                    \nDetected at iteration %d\n\n", \
                    res, i, j, c);
                i = 899;
                break;
            }
        }
    }
    return 0;
}

P.S.: If the memory consumption is the cornerstone for you, feel free to experiment with variable types.


UPDATE from 06 May 2012:

There is something wrong with 'is_palindrome' method.
I did a simple test:

#include <stdio.h>
#include <stdbool.h>
bool is_palindrome(unsigned int const num) {
    unsigned int res = 0;
    unsigned int n = num;
    while(n > res) {
        res = res*10 + n%10;
        n /= 10;
    }
    return n == res;
}

int main() {
    int i;
    for(i = 100; i < 600; ++i) {
        if(is_palindrome(i))
            printf("%d\n", i);
    }
    return 0;
}

And the output was:
110
220
330
440
550

But 111, 222, 212, 585 etc. are palindromic numbers too!

No comments:

Post a Comment