Leetcode 1017: Convert to Base -2

Input: You are given a non-negative integer n.

Example: n = 5

Constraints:

• 0 <= n <= 10^9

Output: Return the binary representation of n in base -2 as a string.

Example: Output: '1101'

Constraints:

• The output should be a binary string with no leading zeros unless the result is '0'.

Goal: The goal is to convert the integer n into a binary representation in base -2.

Steps:

• While n is non-zero, repeatedly divide n by -2 and record the remainders.

• At each step, append the remainder (0 or 1) to the result string.

• For negative n, adjust the division to ensure the remainder is correctly calculated.

Goal: Consider the constraints of n, as the number can be as large as 10^9.

Steps:

• n is a non-negative integer, where 0 <= n <= 10^9.

Assumptions:

• The input value n is guaranteed to be a valid non-negative integer.

• Input: Input: n = 2

• Explanation: In base -2, 2 is represented as '110', since (-2)^2 + (-2)^1 = 2.

• Input: Input: n = 3

• Explanation: In base -2, 3 is represented as '111', since (-2)^2 + (-2)^1 + (-2)^0 = 3.

• Input: Input: n = 4

• Explanation: In base -2, 4 is represented as '100', since (-2)^2 = 4.

Approach: The solution uses repeated division by -2, adjusting for negative remainders, and constructs the binary representation step by step.

Observations:

• We need to handle negative bases while ensuring that the binary representation is valid.

• The key challenge is ensuring that the remainder during division is correctly computed for base -2, especially for negative n.

Steps:

• 1. Initialize an empty string to store the result.

• 2. While n is non-zero, perform the following steps:

• a. Compute the remainder when n is divided by -2.

• b. Append the remainder (either 0 or 1) to the result string.

• c. Adjust n for the next iteration using integer division by -2.

• 3. If the result string is empty, return '0'. Otherwise, return the result string.

Empty Inputs:

• When n is 0, the output should be '0'.

Large Inputs:

• When n is very large (e.g., 10^9), the solution should still work efficiently without exceeding time or space limits.

Special Values:

• Ensure that the result does not contain leading zeros unless the value of n is 0.

Constraints:

• The solution must handle n up to 10^9 without performance issues.

string baseNeg2(int n) {
    string res = "";

    while(n) {
        res = to_string(n&1) + res;
        n = -(n >> 1);
    }

    return res == ""? "0":res;
}

1 : Function Declaration

string baseNeg2(int n) {

Declares the function `baseNeg2` that takes an integer `n` as input and returns a string representing the base -2 representation of `n`.

2 : Variable Initialization

    string res = "";

Initializes an empty string `res` to store the result of the base -2 conversion.

3 : While Loop Start

    while(n) {

Starts a while loop that continues until `n` becomes 0. The loop will calculate the binary digits of `n` in base -2.

4 : Binary Calculation

        res = to_string(n&1) + res;

Calculates the least significant bit (LSB) of `n` by performing a bitwise AND with 1 (`n & 1`), converts it to a string, and appends it to the front of `res`.

5 : Shift and Negate

        n = -(n >> 1);

Performs a right shift on `n` by 1 bit (`n >> 1`) to prepare for the next iteration. The result is negated (`-`) because the number is in base -2.

6 : Return Statement

    return res == ""? "0":res;

Checks if the result string `res` is empty (which means the input was 0) and returns "0". Otherwise, it returns the constructed base -2 representation stored in `res`.

Best Case: O(log n)

Average Case: O(log n)

Worst Case: O(log n)

Description: The time complexity is O(log n) since the number of divisions required is proportional to the logarithm of n.

Best Case: O(log n)

Worst Case: O(log n)

Description: The space complexity is O(log n) due to the space needed for storing the binary representation of n.

Leetcode 1017: Convert to Base -2

Explore →