Leetcode 1256: Encode Number

https://leetcode.com/contest/biweekly-contest-13/problems/encode-number/

Notes:

The key is to find the rules.
The number is encoded firstly with 2^0 + 2^1 + 2^2 + ... + 2^n, then the remainder is encoded into binary 0 or 1.

For example, n = 6.

The first step: n = 2^0 + 2^1 + 3. So the remainder is 3.

Then convert the remainder 3 to "11".

Let us see another example, n = 7.

The first step: n = 2^0 + 2^1 + 2^2. Then the remainder is 0 in this case.

One way to solve this problem, we can always take the last term, then convert it into binary form. From the last term, we can also determine the number of digit in the final binary result. For example, for n = 7, the last term is 2^2, so the final result should have 3 digit.

See the code below:

class Solution {
public:
    string encode(int num) {
        long sum = 0, indx = 0;
        while(sum + pow(2, indx) < (long) num) {
            sum += (long) pow(2, indx);
            ++indx;
        }
        num -= sum;//the last term
        string res = "";
        while(indx > 0) {//number of digits in the binary form
            res.push_back(num%2+'0');
            num /= 2;
            --indx;
        }
        if(num>0) res.push_back('0');//corner case, for example n= 7 vs n = 8
        reverse(res.begin(), res.end());
        return res;
    }
};