LeetCode: Convert to Base -2

Convert to Base -2

Similar Problems:

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups
• Tag: #bitmanipulation, #classic, #baseconversion

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

Note:

• 0 <= N <= 10^9

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:

// https://code.dennyzhang.com/convert-to-base-2
// Basic Ideas:
//
// base * value + reminder = old
//   0 <= reminder < abs(base)
//
// Complexity: Time O(log(n)), Space O(log(n))
import "strconv"
func baseNeg2(N int) string {
    // corner case
    if N == 0 { return "0" }
    res := ""
    for N != 0 {
        reminder := N%(-2)
        N = N/(-2)
        if reminder < 0 {
            reminder += 2
            N += 1
        }
        res = strconv.Itoa(reminder) + res
    }
    return res
}