LeetCode-Solutions/C++/convert-to-base-2.cpp at master · ak-aether/LeetCode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Time:  O(logn)
// Space: O(1)

class Solution {
public:
    string baseNeg2(int N) {
        string result;
        while (N) {
            result += to_string(-N & 1);  // N % -2
            N = -(N >> 1);  // N /= -2
        }
        reverse(result.begin(), result.end());
        return result.empty() ? "0" : result;
    }
};

// Time:  O(logn)
// Space: O(1)
class Solution2 {
public:
    string baseNeg2(int N) {
        static const int BASE = -2;
        string result;
        while (N) {
            int r = N % BASE;
            if (r < 0) {
                r -= BASE;
                ++N;
            }
            result += to_string(r);
            N /= BASE;
        }
        reverse(result.begin(), result.end());
        return result.empty() ? "0" : result;
    }
};