Faithful Numbers

A number is called faithful if you can write it as the sum of distinct powers of 7.

e.g., 2457 = 7 + 72 + 74 . If we order all the faithful numbers, we get the sequence 1 = 70, 7 = 71, 8 = 70 + 71, 49 = 72, 50 = 70 + 72 . . . and so on.

Given some value of N, you have to find the N’th faithful number.

• Time : O(logn)
• Space : O(1)

class Solution {
public:
    long long nthFaithfulNum(int N) {
        long long res = 0, i = 0;
        while(N) {
            if(N & 1) res += pow(7, i);
            N/=2;
            i++;
        }
        return res;
    }
};