[C++] Project Euler #62 - Cubic Permutations

This problem is rated at a difficulty level of 15%.

Surprisingly, I solved it quite easily (using a brute-force method).

The problem asks for the smallest number among five different cube numbers that are made up of the same digits.

---

cube numbers

To be honest, if you were to solve this problem properly, you’d need to check that exactly five such numbers exist, but I didn’t go that far.

I also excluded cases where a digit appears four times or more. Strictly speaking, that shouldn’t be allowed, but because of the way I stored data in an array, I had to exclude such cases. Maybe using a hash map would have been better. That way, I could’ve handled numbers with 6 digits, 7 digits, etc., that have exactly five permutations made up of the same digits and allow digits to appear more than three times. But I tend to avoid using complex data structures, probably because I don’t usually use STL or built-in structures unless they’re absolutely necessary.

Below is the program I wrote.

//------------------------------------------------
//    Project Euler #62 - Cubic Permutations
//        - by Aubrey Choi
//        - created at 2015-10-01
//------------------------------------------------
#include <stdio.h>
#include <time.h>
#include <stdint.h>

int index(int64_t n)
{
    int cnt[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    while( n )
    {
        cnt[n%10]++;
        n /= 10;
    }
    int idx = 0;
    for( int i = 0 ; i < 10 ; i++ )
    {
        if( cnt[i] >= 4 ) return 0;
        idx <<= 2;
        idx |= cnt[i];
    }
    return idx;
}

void solve1()
{
    static int count[1<<20], value[1<<20];

    for( int i = 300 ; ; i++ )
    {
        int64_t cube = (int64_t)i*i*i;
        int idx = index(cube);
        if( idx == 0 ) continue;
        if( count[idx] == 4 ) 
        { 
            int64_t v = value[idx];
            printf("Ans = %lld(%lld)\n", v*v*v, v); 
            break; 
        }
        if( count[idx] == 0 ) value[idx] = i;
        count[idx]++;
    }
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}