Wednesday, August 3, 2016

Project Euler #32 Pandigital numbers - C

Here we go:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
#define LL long long
#define DEBUG 0

using namespace std;

int is_pandigital(LL M1, LL M2, LL P);
int N;

int main() {
    cin >> N;
    LL M1, M2, P;
    LL count = 0;
    LL i, j;
    int DM1, DM2, DP;
    int * flag = (int *) calloc (10000, sizeof(int));
    for(i=1;;i++) {
        M1 = i;
        DM1 = log10(i) + 1;
        #if DEBUG
            cout << "M1: " << M1 << endl;
            cout << "M1 digit: " << DM1 << endl;
        #endif
        if (DM1 >= N-2) {
            break;
        }
        for(j=i+1;;j++) {
            M2 = j;
            DM2 = log10(j) + 1;
            #if DEBUG
                cout << "M2: " << M2 << endl;
                cout << "M2 digit: " << DM2 << endl;
            #endif
            if (DM1 + DM2 >= N-1) {
                break;
            }
            P = M1 * M2;
            DP = log10(P) + 1;
            #if DEBUG
                cout << "P: " << P << endl;
                cout << "P digit: " << DP << endl;
            #endif
            if (DM1 + DM2 + DP != N) {
                continue;
            }
            if (is_pandigital(M1, M2, P)) {
                if (!flag[P]) {
                    flag[P] = 1;
                    count += P;
                }
            }
        }
    }
    free(flag);
    cout << count << endl;
}

int is_pandigital(LL M1, LL M2, LL P) {
    int *digit = (int *)calloc(10, sizeof(int));
    #if DEBUG
        cout << "M1: " << M1 << " M2: " << M2 << " P: " << P << endl;
    #endif
    while (M1 > 0) {
        int cur = M1%10;
        if (cur > N || cur == 0) {
            return 0;
        }
        digit[cur]++;
        if (digit[cur] > 1) {
            return 0;
        }
        M1 /= 10;
    }

    while (M2 > 0) {
        int cur = M2%10;
        if (cur > N || cur == 0) {
            return 0;
        }
        digit[cur]++;
        if (digit[cur] > 1) {
            return 0;
        }
        M2 /= 10;
    }

    while (P > 0) {
        int cur = P%10;
        if (cur > N || cur == 0) {
            return 0;
        }
        digit[cur]++;
        if (digit[cur] > 1) {
            return 0;
        }
        P /= 10;
    }

    for (int i=1; i<N; i++) {
        if (digit[i] != 1) {
            return 0;
        }
    }
    return 1;
}