Convert to Base -2

Medium Bit Manipulation Basics Original on LeetCode

Reported atAirbnb

Convert to Base -2 is a medium bit manipulation problem solved with the basics pattern. The best approach, optimal (alternating-bit mask), runs in O(log n) time and O(log n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try bit patterns in increasing order) up.

Problem

Given a non-negative integer n, return its representation in base -2 as a string of 0s and 1s. In base -2 the digit at position i (counting from the right, starting at 0) is worth (-2)^i, so the weights are 1, -2, 4, -8, 16, ....

The result must have no leading zeros, except that 0 itself is written as "0".

Examples

Example 1

Input
n = 6
Output
"11010"
Why
(-2)^4 + (-2)^3 + (-2)^1 = 16 - 8 - 2 = 6.

Example 2

Input
n = 5
Output
"101"
Why
(-2)^2 + (-2)^0 = 4 + 1 = 5.

Example 3

Input
n = 0
Output
"0"
Why
Zero is written as a single digit.

Constraints

  • 0 <= n <= 10^9

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try bit patterns in increasing order)O(n log n)O(log n)
Repeated division by -2O(log n)O(log n)
Optimal (alternating-bit mask)O(log n)O(log n)

1Brute force (try bit patterns in increasing order)

TimeO(n log n)The answer has about log n digits, so the matching pattern is at most a constant times n and each pattern is evaluated in O(log n).
SpaceO(log n)The output string.

Every bit pattern is a base -2 number. Enumerate patterns 1, 2, 3, ... (as ordinary binary), evaluate each with weights 1, -2, 4, -8, ... and stop at the first one whose value is n. Representations are unique, so that pattern is the answer.

  1. If n is 0, return "0".
  2. For mask = 1, 2, 3, ...: sum the weights (-2)^i of its set bits.
  3. When the sum equals n, return the mask written in binary.
class Solution {
    public String baseNeg2(int n) {
        if (n == 0) return "0";
        for (long mask = 1; ; mask++) {
            long value = 0, weight = 1;
            for (long m = mask; m > 0; m >>= 1) {
                if ((m & 1) == 1) value += weight;
                weight *= -2;
            }
            if (value == n) return Long.toBinaryString(mask);
        }
    }
}

2Repeated division by -2

TimeO(log n)Each step divides the magnitude by about 2.
SpaceO(log n)The digits of the answer.

Just like ordinary base conversion, the lowest digit is n mod 2 (0 or 1). Remove it, and what remains is divisible by -2; dividing by -2 shifts every remaining digit down one position. Repeat until the number becomes 0. The intermediate value may go negative, which is fine.

  1. If n is 0, return "0".
  2. While n != 0: r = n & 1; append r; n = (n - r) / -2.
  3. Reverse the collected digits.
class Solution {
    public String baseNeg2(int n) {
        if (n == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (n != 0) {
            int r = n & 1;
            sb.append(r);
            n = (n - r) / -2;
        }
        return sb.reverse().toString();
    }
}

3Optimal (alternating-bit mask)

TimeO(log n)Constant arithmetic plus writing out about log n digits.
SpaceO(log n)The output string.

Read the answer as an ordinary binary number B. Its base -2 value is B minus twice the bits at odd positions, that is B - 2 * (B & M) where M = ...1010 has 1s at all odd positions. Solving for B gives B = (n + M) ^ M: adding M pays in advance for every odd position, and the XOR flips those positions back. Use 64-bit arithmetic since n + M exceeds 32 bits.

  1. Let M = 0xAAAAAAAA (1s at positions 1, 3, 5, ..., 31).
  2. Compute B = (n + M) XOR M with 64-bit integers.
  3. Return B in ordinary binary ("0" when B is 0).
class Solution {
    public String baseNeg2(int n) {
        long mask = 0xAAAAAAAAL;
        long bits = (n + mask) ^ mask;
        return Long.toBinaryString(bits);
    }
}

Edge cases to test

  • n = 0 must return "0", not an empty string
  • n = 1
  • Powers of two at odd positions (for example 2 needs the digits 110)
  • The largest n, whose answer needs more than 31 digits

Hints

Hint 1

Digit i is worth (-2)^i: positive at even positions, negative at odd positions. The last digit must still equal n mod 2.

Hint 2

Take the last digit r = n & 1, subtract it and divide the rest by -2; repeat until nothing is left.

Hint 3

A one-line trick exists: with the mask that has 1s at all odd positions, (n + mask) ^ mask is the answer read in ordinary binary.

FAQ

What is the best time complexity for Convert to Base -2?

Optimal (alternating-bit mask) runs in O(log n) time and O(log n) extra space. Constant arithmetic plus writing out about log n digits.

Which pattern does Convert to Base -2 use?

It is a bit manipulation problem that uses the basics pattern. Other problems with the same pattern: Decimal to binary, Convert Binary Number in a Linked List to Integer, K-th Bit is Set or Not.

Is there a brute force solution for Convert to Base -2?

Yes. Brute force (try bit patterns in increasing order) takes O(n log n) time and O(log n) space. Every bit pattern is a base -2 number.

Which edge cases should I test for Convert to Base -2?

n = 0 must return "0", not an empty string; n = 1; Powers of two at odd positions (for example 2 needs the digits 110); The largest n, whose answer needs more than 31 digits.