题目描述

给定一个数字 N，返回一个由 "0" 和 "1" 组成的字符串，表示在 -2 进制下它的值。

返回的字符串不含有前导零，除非这个字符串就是 "0"。

样例

输入：2
输出："110"
解释：(-2) ^ 2 + (-2) ^ 1 = 2

输入：3
输出："111"
解释：(-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3

输入：4
输出："100"
解释：(-2) ^ 2 = 4

注意

• 0 <= N <= 10^9

算法

(短除法) $O(\log N)$

1. 类似于十进制转二进制的做法，我们仍然采用短除法，每次除以 -2，记录余数。
2. 这里要求余数必须是正的，最后循环退出条件是 N 变为了 1。注意特判 N 为 0。

时间复杂度

• 每次都除以 -2，故时间复杂度为 $O(\log N)$。

空间复杂度

• 需要字符串记录余数，故空间复杂度为 $O(\log N)$。

C++ 代码

class Solution {
public:
    string baseNeg2(int N) {
        if (N == 0)
            return "0";
        string s = "";
        while (N != 1) {
            if (N < 0) {
                if (N % 2 == 0) {
                    s += "0";
                    N = -N / 2;
                }
                else {
                    s += "1";
                    N = -N / 2 + 1;
                }
            } else {
                if (N % 2 == 0) {
                    s += "0";
                    N = -N / 2;
                }
                else {
                    s += "1";
                    N = -N / 2;
                }
            }
        }
        s += "1";
        reverse(s.begin(), s.end());
        return s;
    }
};