[C/C++] Project Euler #36 - Double-base Palindromes

Project Euler Problem #36 - “Double-base Palindromes” is about finding numbers that are palindromic in both decimal and binary representations.  For example, 585 is a palindrome in decimal (585) and also a palindrome in binary (1001001).  The task is to find such numbers, calculate their sum, and output the result.

There are various ways to determine if a number is a palindrome and to generate palindromic numbers.

In this problem, we need to find numbers that are palindromic in decimal and also in binary, then compute their sum.  This is a 5% difficulty problem (which means it is relatively simple).

While there are many ways to generate palindromic numbers in decimal, I used a slightly more complex method to generate them.  My goal was to speed up the process.

For example, given the number 13, its palindromic numbers can be generated as 3113 and 31013.  To do this, I first create the reverse of 13, which is 31. Then I use calculations like 31 x 100 + 13 and 31 x 1000 + 13 to generate the palindromic numbers. This way, I can generate all palindromic numbers below one million. While it is possible to use a simple for loop to check if each number between 1 and one million is palindromic in both decimal and binary, my method reduces the number of tests needed by focusing only on binary checks. However, since a range of one million isn’t that large, you can opt for the simpler approach if you prefer (no need to overthink it).

 

palindromes

Below is the source code I wrote.

//------------------------------------------------
//    Project Euler #36 - Double-base Palindromes
//        - by Aubrey Choi
//        - created at 2015-03-21
//------------------------------------------------
#include <stdio.h>

bool IsPalindrome2(int n);

int main()
{
    int ans = 0;

    for( int i = 1 ; i < 10 ; i += 2 )
    {
        if( IsPalindrome2(i*11) ) ans += i*11;
        if( IsPalindrome2(i*1001) ) ans += i*1001;
        if( IsPalindrome2(i*100001) ) ans += i*100001;
    }
    for( int i = 11 ; i < 100 ; i += 2 )
    {
        int t = (i/10)+(i%10)*10;
        if( IsPalindrome2(t*100+i) ) ans += t*100+i;
        if( IsPalindrome2(t*10000+i) ) ans += t*10000+i;
    }
    for( int i = 101 ; i < 1000 ; i += 2 )
    {
        int t = (i/100)+((i/10)%10)*10+(i%10)*100;
        if( IsPalindrome2(t*1000+i) ) ans += t*1000+i;
    }
    for( int i = 1 ; i < 10 ; i += 2 )
        if( IsPalindrome2(i) ) ans += i;
    for( int i = 1 ; i < 10 ; i += 2 )
    {
        for( int j = 0 ; j < 10 ; j++ )
        {
            if( IsPalindrome2(i*101+j*10) ) ans += i*101+j*10;
            if( IsPalindrome2(i*10001+j*100) ) ans += i*10001+j*100;
        }
    }
    for( int i = 11 ; i < 100 ; i += 2 )
    {
        int t = (i/10)+(i%10)*10;
        for( int j = 0 ; j < 10 ; j++ )
        {
            if( IsPalindrome2(t*1000+i+j*100) ) ans += t*1000+i+j*100;
        }
    }
    printf("ans = %d\n", ans);
}

bool IsPalindrome2(int n)
{
    int s = 0;
    int t = n;
    while( t ) { s = (s<<1)|(t&1); t>>=1; }
    if( s != n ) return false;
    return true;
}