LeetCode - 1017. Convert to Base -2

Given a number N, return a string consisting of "0"s and "1"s that represents its value in base -2 (negative two).

The returned string must have no leading zeroes, unless the string is “0”.

Example 1:

Input: 2
Output: “110”
Explantion: (-2) ^ 2 + (-2) ^ 1 = 2

Example 2:

Input: 3
Output: “111”
Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3

Example 3:

Input: 4
Output: “100”
Explantion: (-2) ^ 2 = 4

算法

代码

char* baseNeg2(int N) {
    int a = N;
    if(a==0){
        return "0";
    }
    int num = 0;
    char* result = (char*)malloc(sizeof(char));
    result[0] = '\0';
    while(a!=0){
        int tmp = a/(-2);
        int k = a%(-2);
        num++;
        if(k<0){
            k = 2+k;
            tmp++;
        }
        result = (char*)realloc(result,(num+1)*sizeof(char));
        result[num] = '0'+k;
        a = tmp;
    }
    int i;
    char* result2 = (char*)malloc((num+1)*sizeof(char));
    for(i = 0;i<num+1;i++){
        result2[i] = result[num-i];
    }
    return  result2;
}