1017. Convert to Base -2


Problem Description

The problem requires us to convert a given integer n into its equivalent representation in base -2. Base -2 numbering system, also known as negabinary, is similar to binary except that the base is -2 instead of 2. This means that each digit position is worth -2 raised to the power of the position index, starting from 0. The challenge is to represent any integer n with digits 0 and 1 in base -2 such that there are no leading zeros, except when the resulting string should be "0".

Intuition

The solution is derived using a similar approach to converting numbers from decimal to binary, with some modifications due to the negative base. The conventional method to convert a decimal number to binary involves repeatedly dividing the number by 2 and taking the remainder as the next digit. The process continues until the number is completely reduced to 0. In the case of the negabinary system, we continue to divide by -2, but we need to handle negative remainders differently.

When converting to negabinary, if the remainder when dividing by -2 is negative, we adjust the number by adding 1 to prevent the use of negative digits. Since we're working with a negative base, adding 1 effectively subtracts the base from the original number, which in turn cancels out the negative remainder and keeps the number non-negative.

Each division gives us one binary digit, but due to the nature of base -2, we sometimes need to increment the quotient to handle the cases where the remainder would otherwise be negative. The pattern of division continues until the dividend (our number n) becomes zero. The algorithm appends '1' if the expression n % 2 evaluates to true (i.e., remainder is 1 when dividing by 2), which indicates that our current digit in negabinary is 1. Otherwise, it appends '0'. After each step, n is divided by 2 and k, which toggles between 1 and -1, is used to adjust n accordingly. The sequence of 1s and 0s is reversed at the end to get the final negabinary representation.

Learn more about Math patterns.

Solution Approach

The Solution class defines a single method baseNeg2, which takes an integer n as input and returns a string representing the negabinary representation of that integer.

Here's how the implementation works:

  • We initialize a variable k with the value 1. This will be used to alternate the subtraction value between 1 and -1 according to the negabinary rules.
  • We create an empty list ans that will eventually contain the digits of the negabinary number, albeit in reverse order.
  • We enter a while loop that will keep running until n is reduced to zero. On each iteration, we perform the following steps:
    • Check if n % 2 is 1 or 0 by using the modulo operator. This is equivalent to finding out if there is a remainder when n is divided by 2:
      • If n % 2 evaluates to 1, it means the current binary digit should be '1', and we append '1' to the ans list.
      • Furthermore, we adjust n by subtracting k. Since the base is negative, when the remainder is 1, we need to compensate by decrementing n by 1 when k is 1 or incrementing by 1 when k is -1. This ensures we are correctly building the negabinary representation.
      • If n % 2 evaluates to 0, we simply append '0' to the ans list. There is no need to adjust n since the remainder is 0.
    • Update n to be half of its previous value, which is done by using integer division n //= 2. Integer division truncates towards zero, making sure that we are getting closer to zero on each division.
    • Multiply k by -1. This simple operation alternates the value of k between 1 and -1, ensuring that we properly adjust n in the next iteration to account for the negative base.
  • Once the while loop exits, we reverse the ans list to represent the digits in the correct order since we've been appending them in reverse.
  • We then join the list into a string to represent the negabinary number. If the list is empty, which would occur if n were 0, we return '0'.

By the end of the loop, the ans list will contain the negabinary digits in reverse order, so we need to reverse it to get the correct representation. We perform this reverse operation using ans[::-1]. If the number n is 0, then ans will be an empty list, in which case we return '0'.

The Python join function concatenates the elements of the list into a single string, which is the final negabinary representation we return from our method.

This approach cleverly utilizes modular arithmetic and the property of negabinary representation to efficiently convert an integer to its equivalent in base -2. No additional data structures besides the list ans are used, and the entire conversion happens in a single pass through the loop with an O(log n) time complexity.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach by converting the decimal number 6 to its equivalent in base -2.

  1. Start with n = 6 and initialize k = 1.
  2. Initialize an empty list ans which will hold the digits of the negabinary number in reverse order.

The while-loop begins:

  • Iteration 1:

    • n % 2 is 0 (since 6 is even), so we append '0' to ans. (ans = ['0'])
    • We do not adjust n because there is no remainder.
    • Now, perform integer division n //= 2, which gives n = 3.
    • Multiply k by -1 to get k = -1.
  • Iteration 2:

    • n % 2 is 1, so we append '1' to ans. (ans = ['0', '1'])
    • Adjust n by subtracting -1 (since k = -1), giving us n = 3 - (-1) = 4.
    • Perform integer division n //= 2, yielding n = 2.
    • Multiply k by -1 to get k = 1.
  • Iteration 3:

    • n % 2 is 0, so we append '0' to ans. (ans = ['0', '1', '0'])
    • n does not need adjustment as the remainder is 0.
    • Perform integer division n //= 2, which results in n = 1.
    • Multiply k by -1 to get k = -1.
  • Iteration 4:

    • n % 2 is 1, so we append '1' to ans. (ans = ['0', '1', '0', '1'])
    • Adjust n by subtracting -1 (since k = -1), which makes n = 1 - (-1) = 2.
    • Perform integer division n //= 2, yielding n = 1.
    • Multiply k by -1 to get k = 1.
  • Iteration 5:

    • n % 2 is 1, so we append '1' to ans. (ans = ['0', '1', '0', '1', '1'])
    • Adjust n by subtracting 1 (since k = 1), which leaves n = 1 - 1 = 0.
    • The division step and multiplication of k by -1 are no longer necessary as n is now 0, so the while loop terminates.

Now, ans = ['0', '1', '0', '1', '1'] holds the negabinary digits in reverse order. To fix this, we reverse ans to get ['1', '1', '0', '1', '0'].

Finally, join all elements of the list ans to get the string '11010', which is the negabinary representation of the decimal number 6.

Thus, the baseNeg2 method would return '11010' when called with the input 6.

Solution Implementation

1class Solution:
2    def baseNeg2(self, n: int) -> str:
3        # Initialize a variable to keep track of the power of (-2)
4        power_of_neg_2 = 1
5        # List to store the digits of the result
6        result_digits = []
7      
8        # Continue the loop until n becomes 0
9        while n:
10            # Check if the current bit is set (if n is odd)
11            if n % 2:
12                # If the bit is set, append '1' to the result digits array
13                result_digits.append('1')
14                # Since the base is -2, when a '1' is added at this power, we need to subtract
15                # the power of (-2) to balance the actual value.
16                n -= power_of_neg_2
17            else:
18                # If the bit is not set, append '0' to the result digits array
19                result_digits.append('0')
20            # Divide n by 2 (shift right), this will move to the next bit
21            n //= 2
22            # Multiply the power by -1 because each time we move one position to the left
23            # in base -2 notation, the power of the digit alternates signs
24            power_of_neg_2 *= -1
25      
26        # Since we've been appending digits for the least significant bit (LSB) to the most
27        # significant bit (MSB), we need to reverse the array to get the correct order.
28        # If there are no digits in the result, return '0'.
29        return ''.join(reversed(result_digits)) or '0'
30
1class Solution {
2    public String baseNeg2(int number) {
3        // If number is 0, the base -2 representation is also "0".
4        if (number == 0) {
5            return "0";
6        }
7      
8        // StringBuilder used to build the result from right to left.
9        StringBuilder result = new StringBuilder();
10      
11        // Variable to alternate the sign (k = 1 or k = -1).
12        int signAlteration = 1;
13      
14        // Continue looping until the number is reduced to 0.
15        while (number != 0) {
16            // Checking the least significant bit of 'number'.
17            if (number % 2 != 0) {
18                // If it's 1, append "1" to the result and subtract the sign alteration from number.
19                result.append(1);
20                number -= signAlteration;
21            } else {
22                // If it's 0, append "0" to the result (nothing gets subtracted from number).
23                result.append(0);
24            }
25          
26            // Alternate the sign for next iteration.
27            signAlteration *= -1;
28          
29            // Divide the number by 2 (right shift in base -2 system).
30            number /= 2;
31        }
32      
33        // Since we've been building the result in reverse, we need to reverse the order now.
34        return result.reverse().toString();
35    }
36}
37
1#include <algorithm> // For reverse function
2#include <string>    // For string class
3
4class Solution {
5public:
6    // Function returns the base -2 representation of the integer n as a string.
7    string baseNeg2(int n) {
8        // When n is 0, the base -2 representation is just "0".
9        if (n == 0) {
10            return "0";
11        }
12
13        // Initialize an empty string to build the base -2 representation.
14        string baseNeg2Representation;
15
16        // Helper variable to keep track of the alternating signs when dividing by -2.
17        int alternatingSignFactor = 1;
18
19        // Process the number n until it becomes 0.
20        while (n != 0) {
21            // Examine the least significant bit (LSB) to determine whether to place 1 or 0.
22            // If LSB is 1 (odd number), add '1' to the representation.
23            if (n % 2 == 1) {
24                baseNeg2Representation.push_back('1');
25                // Adding alternatingSignFactor (which is either +1 or -1) ensures
26                // we either increase or decrease n to make n divisible by 2,
27                // which helps with the next division.
28                n -= alternatingSignFactor;
29            }
30            // If LSB is 0 (even number), add '0' to the representation.
31            else {
32                baseNeg2Representation.push_back('0');
33            }
34
35            // Negate the alternatingSignFactor to handle base of -2.
36            alternatingSignFactor *= -1;
37
38            // Integer division by 2 to remove the processed bit.
39            n /= 2;
40        }
41
42        // The constructed string needs to be reversed because we started from LSB to MSB.
43        reverse(baseNeg2Representation.begin(), baseNeg2Representation.end());
44
45        return baseNeg2Representation;
46    }
47};
48
1function baseNeg2(n: number): string {
2    // If the input number is zero, return '0' as the base -2 representation.
3    if (n === 0) {
4        return '0';
5    }
6
7    // Initialize the power of -2 to 1 (since (-2)^0 is 1).
8    let powerOfNegTwo = 1;
9
10    // An array to store the binary digits of the base -2 representation.
11    const baseNegTwoDigits: string[] = [];
12
13    // Iterate until n doesn't become zero.
14    while (n) {
15        // If n is odd, append '1' to the digits array and decrement n by the current powerOfNegTwo.
16        if (n % 2) {
17            baseNegTwoDigits.push('1');
18            n -= powerOfNegTwo;
19        } else {
20            // If n is even, append '0' to the digits array.
21            baseNegTwoDigits.push('0');
22        }
23
24        // Alternate the sign of the powerOfNegTwo (-1, 1, -1, 1,...) as we go to higher powers.
25        powerOfNegTwo *= -1;
26
27        // Integer division by 2, Math.trunc discards the decimal part.
28        n = Math.trunc(n / 2);
29    }
30
31    // Reverse the digits and join them to return the string representation of base -2 number.
32    return baseNegTwoDigits.reverse().join('');
33}
34

Time and Space Complexity

The time complexity of the given code is O(log(n)). This is because the loop iterates once for every bit that n produces when converging to 0. Since we're halving n at every step, albeit with an additional operation to account for negative base representation, the number of iterations grows logarithmically with respect to the input n.

The space complexity is O(log(n)) as well, this is due to the ans list that is used to store the binary representation of the number in base -2. The number of digits needed to represent n in base -2 scales similarly to the number of iterations, hence the space complexity follows the same logarithmic pattern.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄