Convert to Base -2 solution and explanation
GoogleThe problem
Given an integer n, return a binary string representing its representation in base -2.
Note that the returned string should not have leading zeros unless the string is "0".
Example 1:
Input: n = 2 Output: "110" Explantion: (-2)2 + (-2)1 = 2
Example 2:
Input: n = 3 Output: "111" Explantion: (-2)2 + (-2)1 + (-2)0 = 3
Example 3:
Input: n = 4 Output: "100" Explantion: (-2)2 = 4
Constraints:
0 <= n <= 109
Approach overview
Problem Overview: You are given an integer n and need to return its representation in base -2. Unlike normal base conversion, the base is negative, which changes how division and remainders behave while building the digit sequence.
Approach 1: Iterative Division by -2 (O(log n) time, O(log n) space)
The core idea mirrors standard base conversion: repeatedly divide the number by the base and collect remainders. The complication is that dividing by -2 can produce negative remainders. To keep digits valid (0 or 1), you adjust the remainder whenever it becomes negative.
At each step, compute remainder = n % -2. If the remainder is negative, add 2 to it and adjust the quotient using n = (n - remainder) / -2. This ensures every digit is either 0 or 1. Append the remainder to the result and continue until n becomes 0. Since each division roughly halves the magnitude of n, the loop runs about log2(n) times.
This method relies purely on arithmetic properties of negative bases and fits naturally into problems involving math and number theory. The digits are generated from least significant to most significant, so reverse the collected sequence before returning the final string.
Approach 2: Recursive Base -2 Conversion (O(log n) time, O(log n) space)
A recursive formulation follows the same math but expresses the repeated division as a recursive call. Compute the remainder for the current step, normalize it to 0 or 1, then recursively convert the updated quotient (n - remainder) / -2. Each recursive call contributes one digit.
The recursion depth is proportional to the number of digits in the base -2 representation, which is O(log n). While the logic is elegant, recursion adds call stack overhead and is less common in interview solutions compared to the iterative loop.
Recommended for interviews: Iterative division by -2. Interviewers expect you to adapt the standard base-conversion pattern and correctly handle negative remainders. Demonstrating the remainder adjustment shows a clear understanding of how negative bases behave mathematically.
Approach 1: Iterative Division by -2
In this approach, we simulate the traditional base conversion process, but with base -2. For each step, divide the number n by -2, and store the remainder. Update n with the quotient. Make sure to adjust the remainder if it's negative, as this may happen due to the negative base.
The key detail is handling the remainder carefully when it becomes negative, which requires incrementing the quotient.
def base_neg2(n):
if n == 0:
return '0'
result = ''
while n != 0:
n, remainder = divmod(n, -2)
if remainder < 0:
remainder += 2
n += 1
result = str(remainder) + result
return resultpublic class BaseNeg2 {
public static String baseNeg2(int n) {
if (n == 0) return "0";
StringBuilder result = new StringBuilder();
while (n != 0) {
int remainder = n % -2;
n /= -2;
if (remainder < 0) {
remainder += 2;
n += 1;
}
result.insert(0, remainder);
}
return result.toString();
}
}#include <string>
using namespace std;
string baseNeg2(int n) {
if (n == 0) return "0";
string result = "";
while (n != 0) {
int remainder = n % -2;
n /= -2;
if (remainder < 0) {
remainder += 2;
n += 1;
}
result = to_string(remainder) + result;
}
return result;
}function baseNeg2(n) {
if (n === 0) return "0";
let result = "";
while (n !== 0) {
let remainder = n % -2;
n = Math.floor(n / -2);
if (remainder < 0) {
remainder += 2;
n += 1;
}
result = remainder.toString() + result;
}
return result;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* base_neg2(int n) {
if (n == 0) return "0";
char* result = (char*)malloc(32 * sizeof(char));
result[0] = '\0';
int len = 0;
while (n != 0) {
int remainder = n % -2;
n /= -2;
if (remainder < 0) {
remainder += 2;
n += 1;
}
// Prepend the remainder to the result
char digit[2];
sprintf(digit, "%d", remainder);
strcat(digit, result);
strcpy(result, digit);
}
return result;
}using System;
public class BaseNeg2 {
public static string BaseNeg2(int n) {
if (n == 0) return "0";
string result = "";
while (n != 0) {
int remainder = n % -2;
n /= -2;
if (remainder < 0) {
remainder += 2;
n += 1;
}
result = remainder.ToString() + result;
}
return result;
}
}This Python solution uses a loop that continues until n is reduced to zero. In each iteration, the number n is divided by -2, using divmod to get both the quotient and the remainder. If the remainder is negative, it is adjusted by adding 2, and the quotient is incremented to reflect this adjustment. The remainder is accumulated into the result string from right to left, building the base -2 representation.
Time Complexity: O(log2n).
Space Complexity: O(log2n) for storing the result string.
Approach 2: Default Approach
function baseNeg2(n: number): string {
if (n === 0) {
return '0';
}
let k = 1;
const ans: string[] = [];
while (n) {
if (n % 2) {
ans.push('1');
n -= k;
} else {
ans.push('0');
}
k *= -1;
n /= 2;
}
return ans.reverse().join('');
}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)
}impl Solution {
pub fn base_neg2(n: i32) -> String {
if n == 0 {
return "0".to_string();
}
let mut k = 1;
let mut ans = String::new();
let mut num = n;
while num != 0 {
if num % 2 != 0 {
ans.push('1');
num -= k;
} else {
ans.push('0');
}
k *= -1;
num /= 2;
}
ans.chars().rev().collect::<String>()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Division by -2 | Time Complexity: O(log2n). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Division by -2 | O(log n) | O(log n) | Best general solution. Efficient and commonly expected in coding interviews. |
| Recursive Base -2 Conversion | O(log n) | O(log n) | Useful for conceptual clarity or when expressing the conversion process recursively. |
Frequently asked questions
Is Convert to Base -2 easy or hard?
Convert to Base -2 is considered a medium difficulty problem. The logic is short but the tricky part is handling negative remainders correctly when dividing by -2, which often confuses candidates unfamiliar with negative base systems.
Convert to Base -2 Python/Java solution
In Python or Java, implement a loop that repeatedly divides n by -2 while storing adjusted remainders (0 or 1). Append digits to a list or string builder and reverse the result at the end. The algorithm runs in O(log n) time and uses O(log n) space.
How to solve Convert to Base -2 in O(log n)?
Use repeated division by -2. At each step compute the remainder n % -2, normalize it to 0 or 1 by adding 2 if it is negative, then update n = (n - remainder) / -2. Continue until n becomes zero and reverse the collected digits.
What is the best approach for Convert to Base -2?
The best approach is iterative division by -2. Repeatedly divide the number by -2, collect the remainder, and adjust it when the remainder becomes negative so that digits remain 0 or 1. This produces the base -2 representation in O(log n) time.
Is Convert to Base -2 asked at Google/Amazon/Meta?
Problems involving unusual base systems and number transformations appear in interviews at companies like Google and Amazon. They test understanding of mathematical reasoning and careful handling of edge cases in arithmetic algorithms.
What data structure is used in Convert to Base -2?
The solution mainly relies on arithmetic operations, but a dynamic string or list is used to store digits as they are generated. Since digits are produced in reverse order, the structure is reversed at the end to build the final result.
What is the time complexity of Convert to Base -2?
The time complexity is O(log n) because each iteration divides the number by 2 in magnitude. The number of digits in the base -2 representation grows logarithmically with respect to n.