p36_cringe

#include <bits/stdc++.h>
#include <chrono>

using namespace std;

long long total = 1;

int toDec(string s) {
    int ans = 0;
    int len = s.size();
    for (int i = len - 1; i >= 0; i--) {
        int val = (s[i] == '0') ? 0 : pow(2, len - i - 1);
        ans += val;
    }
    return ans;
}

bool isPalindrome(string t) {
    int len = t.size();
    for (int i = 0; i <= len / 2; i++) {
        if (t[i] != t[len - 1 - i]) return 0;
    }
    return 1;
}

void check(string s) {

    string temp, a, b;

    temp = s;
    a = s;
    b = s;

    reverse(s.begin(), s.end());

    temp = temp + s;
    a = a + "0" + s;
    b = b + "1" + s;

    // convert to decimal
    int d1 = toDec(temp);
    int d2 = toDec(a);
    int d3 = toDec(b);

    if (d1 < 1000000 && isPalindrome(to_string(d1))) {
        // cout << d1 << " : " << temp << "\n";
        total += d1;
    }

    if (d2 < 1000000 && isPalindrome(to_string(d2))) {
        // cout << d2 << " : " << a << "\n";
        total += d2;
    }

    if (d3 < 1000000 && isPalindrome(to_string(d3))) {
        // cout << d3 << " : " << b << "\n";
        total += d3;
    }
}

void gen(string s) {
    if (!s.empty()) {
        // process
        check(s);
    }

    if (s.size() == 10) return; // base case

    gen( s + "1");
    gen( s + "0");

}

int main() {

    auto start = std::chrono::steady_clock::now();

    gen("1");

    auto stop = std::chrono::steady_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>((stop - start) / 1000);

    cout << "Time taken by function: " << duration.count() << " nanoseconds" << endl;

    cout << total << "\n";
}