SPOJ 11354. Amusing numbers – CPP solution

The idea is notice that the string cannot be bigger than 64 characters due to constraints.
You calculate how big the length of the string should be – say L.
Then you generate a string of length L and set only 5s.
Then iterate and change the 5 to a 6. Find how many numbers are smaller after the change. If count is bigger than K (the index we are searching for), then we should change it back to 5.
Finding the number of smaller numbers is easy. Say that we have generated so far:
Number = 565
Then obviously all numbers of length 2 and 1 are smaller. Namely:
length 1. Numbers are 5 and 6. => Count is 2 which is 1< <1. length 2. Numbers are 55,56,65,66 => count is 4 which is 1< <2 => in general for length L, the count of smaller ones are 2^1 + 2^2 + .. + 2^ (L-1)
Then we have to take in hand all numbers of length L=3. We iterate over the string until we find a 6 and then compute.
In our case, 565.
Then obviously we have the suffix 5, for which we can set whatever 5 or 6. => we have a count of 2^(suffix length).
Solution:

#include <iostream>
using namespace std;

typedef unsigned long long ull;

ull pow[65];
ull sum[65];

int calcLen(ull num) {
    for (int i = 1; i <= 64; ++i) {
        if (sum[i] >= num) return i;
    }
    return 64;
}

ull calcSmaller(int len, char * buf) {
    ull cnt = sum[len-1];
    for (int i = 0; i < len; ++i) {
        if (buf[i] == '6') {
            cnt += pow[len-i-1];
        }
    }
    return cnt;
}

void gen(ull num, int len, char * buf) {
    for (int i = 0; i < len; ++i) buf[i] = '5';
    buf[len] = '\0';
    for (int i = 0; i < len; ++i) {
        buf[i] = '6';
        if (calcSmaller(len, buf) >= num) {
            buf[i] = '5';
        }
    }
}

int main() {
    cin.sync_with_stdio(0);
    for (int i = 1; i<=64; ++i) {
        pow[i] = 1ULL<<i;
        sum[i] = sum[i-1] + pow[i];
    }
    pow[0] = 1ULL;
    int n;
    cin >> n;
    ull num;
    char buf[65];
    while (n--) {
        cin >> num;
        int len = calcLen(num);
        gen(num, len, buf);
        cout << buf << endl;
    }
    return 0;
}