Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1017.html

1017. Convert to Base -2 (Medium)

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:

  1. 0 <= N <= 10^9

Related Topics:
Math

Similar Questions:

Solution 1.

For base 2 the bits represent the following numbers

base(2)  = 1 1 1 1
base(10) = 8 4 2 1

For base -2

base(-2) = 1  1  1 1
base(10) = -8 4 -2 1

So if N base 2 only has ones on even-indexed positions, N base -2 should be the same as N base 2.

Example:

5 base 2 = 101
5 base -2 = 101

If N base 2 has ones on odd-indexed positions, then we can get another one to the one-more-significant digit.

This works because 2^i base 2 is the same as 2^(i + 1) base -2 minus 2^i base -2 where i is odd. For example, when i = 1, 2^i base 2 = 2 is the same as 2^(i+1) base -2 = 4 minus 2^i base -2 = -2.

Example:

2 base 2 = 10
2 base -2 = 110 // add one digit at position 2

3 base 2 = 11
3 base -2 = 111 // add one digit at position 2

7 base 2 = 111
7 base -2 = 11011 // add one digit at position 2, we get 211 = 1011; then we add one digit at position 4, we get 11011
// OJ: https://leetcode.com/problems/convert-to-base-2/
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    string baseNeg2(int N) {
        if (N == 0) return "0";
        string ans;
        while (N) {
            ans += '0' + (N % 2);
            N /= 2;
        }
        int carry = 0;
        for (int i = 0; i < ans.size(); ++i) {
            ans[i] += carry;
            if (ans[i] > '1') {
                ans[i] = '0';
                carry = 1;
            } else carry = 0;
            if (ans[i] == '1' && i % 2) carry += 1;
            if (carry && i == ans.size() - 1) {
                ans += '1';
                carry = 0;
            }
        }
        reverse(begin(ans), end(ans));
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/convert-to-base-2/
// Time: O(logN)
// Space: O(1)
// Ref: https://leetcode.com/problems/convert-to-base-2/discuss/265507/JavaC%2B%2BPython-2-lines-Exactly-Same-as-Base-2
class Solution {
public:
    string baseNeg2(int N) {
        if (N == 0) return "0";
        string ans;
        while (N) {
            ans += '0' + (N & 1);
            N = -(N >> 1); // divide by -2 and round toward -infinity
        }
        reverse(begin(ans), end(ans));
        return ans;
    }
};

Or recursively

// OJ: https://leetcode.com/problems/convert-to-base-2/
// Time: O(logN)
// Space: O(logN)
class Solution {
public:
    string baseNeg2(int N) {
        if (N == 0 || N == 1) return to_string(N);
        return baseNeg2(-(N >> 1)) + to_string(N & 1);
    }
};

Solution 3.

Reference: https://www.geeksforgeeks.org/convert-number-negative-base-representation/

When we get negative r, we add 2 to r and increment N. This works because

r = -1, N = 0
the number is -1

r = 1, N = 1
the number is -2 * 1 - 1 = -1

Example,

N = 3

// first round
r = 3 % -2 = 3 - (3 / -2) * -2 = 3 - (-1 * -2) = 1
N = 3 / -2 = -1

// second round
r = -1 % -2 = -1 - (-1 / -2) * -2 = -1 - (0 * -2) = -1
N = -1 / -2 = 0

// now r is negative, we turn it to be positive
r = -1 + 2 = 1
N = 0 + 1 = 1

// last round
r = 1 % -2 = 1 - (1 / -2) * -2 = 1
N = 1 / -2 = 0

So the result is 111.
// OJ: https://leetcode.com/problems/convert-to-base-2/
// Time: O(logN)
// Space: O(1)
// Ref: https://leetcode.com/problems/convert-to-base-2/discuss/265544/C%2B%2B-Geeks4Geeks
class Solution {
public:
    string baseNeg2(int N) {
        if (N == 0) return "0";
        string ans;
        while (N) {
            int r = N % -2;
            N /= -2;
            if (r < 0) {
                r += 2;
                N++;
            }
            ans += '0' + r;
        }
        reverse(begin(ans), end(ans));
        return ans;
    }
};
  • class Solution {
        public String baseNeg2(int N) {
            if (N == 0)
                return "0";
            int[] bits = new int[32];
            int remain = N;
            int index = 0;
            while (remain > 0) {
                bits[index] = remain % 2;
                remain /= 2;
                index++;
            }
            for (int i = 0; i <= 31; i++) {
                if (i % 2 == 1 && bits[i] == 1)
                    bits[i + 1]++;
                while (bits[i] > 1) {
                    bits[i] -= 2;
                    bits[i + 1]++;
                }
            }
            StringBuffer sb = new StringBuffer();
            boolean flag = false;
            for (int i = 31; i >= 0; i--) {
                int bit = bits[i];
                if (flag)
                    sb.append(bit);
                else {
                    if (bit == 1) {
                        sb.append(bit);
                        flag = true;
                    }
                }
            }
            return sb.toString();
        }
    }
    
    ############
    
    class Solution {
        public String baseNeg2(int n) {
            if (n == 0) {
                return "0";
            }
            int k = 1;
            StringBuilder ans = new StringBuilder();
            while (n != 0) {
                if (n % 2 != 0) {
                    ans.append(1);
                    n -= k;
                } else {
                    ans.append(0);
                }
                k *= -1;
                n /= 2;
            }
            return ans.reverse().toString();
        }
    }
    
  • // OJ: https://leetcode.com/problems/convert-to-base-2/
    // Time: O(logN)
    // Space: O(1)
    class Solution {
    public:
        string baseNeg2(int N) {
            if (N == 0) return "0";
            string ans;
            while (N) {
                ans += '0' + (N % 2);
                N /= 2;
            }
            int carry = 0;
            for (int i = 0; i < ans.size(); ++i) {
                ans[i] += carry;
                if (ans[i] > '1') {
                    ans[i] = '0';
                    carry = 1;
                } else carry = 0;
                if (ans[i] == '1' && i % 2) carry += 1;
                if (carry && i == ans.size() - 1) {
                    ans += '1';
                    carry = 0;
                }
            }
            reverse(begin(ans), end(ans));
            return ans;
        }
    };
    
  • # 1017. Convert to Base -2
    # https://leetcode.com/problems/convert-to-base-2/
    
    class Solution:
        def baseNeg2(self, n: int) -> str:
            res = []
    
            while n != 0:
                res.append(n & 1)
                n = -(n >> 1)
            
            return "".join(map(str, res[::-1] or [0]))
    
    
  • func baseNeg2(n int) string {
    	if n == 0 {
    		return "0"
    	}
    	ans := []byte{}
    	k := 1
    	for n != 0 {
    		if n%2 != 0 {
    			ans = append(ans, '1')
    			n -= k
    		} else {
    			ans = append(ans, '0')
    		}
    		k *= -1
    		n /= 2
    	}
    	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
    		ans[i], ans[j] = ans[j], ans[i]
    	}
    	return string(ans)
    }
    
  • function baseNeg2(n: number): string {
        if (n === 0) {
            return '0';
        }
        let k = 1;
        let ans: string[] = [];
        while (n) {
            if (n % 2) {
                ans.push('1');
                n -= k;
            } else {
                ans.push('0');
            }
            k *= -1;
            n /= 2;
        }
        return ans.reverse().join('');
    }
    
    

All Problems

All Solutions