1073. Adding Two Negabinary Numbers

Problem Description

The given problem deals with the unusual concept of numbers represented in base -2. Unlike standard positive base numbers, in base -2, the value of each digit increases negatively as we move from least significant bit to most significant bit. That means each bit in the base -2 number can contribute a positive or negative value depending on its position. The challenge is to take two such base -2 numbers, arr1 and arr2, and output the sum of these numbers also in base -2 array format. Just as in binary addition, the sum in base -2 could also involve carrying over or borrowing, but with an additional twist due to the negative base.

The provided arrays arr1 and arr2 are the representations of two base -2 numbers where indexes of the array represent the powers of -2 starting from 0 for the least significant bit. Note that there will be no leading zeroes in the numbers given, ensuring the most significant bit is always 1 if the number itself isn't 0.

Intuition

To solve this problem, we need to add two base -2 numbers while carrying over values similar to binary addition, but with modifications for the negative base. We start by setting up a loop from the least significant bit (LSB) to the most significant bit (MSB) of both input arrays, handling cases where one array might be longer than the other. During each iteration, we calculate the sum of the current bits and any previous carry-over.

In base -2, unlike base 2, when we have two '1' bits, adding them would give us '0' and would cause us to 'carry' a -1 to the next more significant bit. This is because 1 + 1 = 2, and in base -2, 2 is represented by a '0' in the current bit and subtracting '1' from the next more significant bit (since it's base -2). We must also handle the scenario where the addition can result in -1, which in base -2 means we need to carry over '+1' to the next bit.

The algorithm in the solution takes the above observations into account. We iterate through the input arrays bit by bit, calculate the sum, adjust the carry-over, and if necessary, continue calculating till all carry-overs are settled. This may sometimes lead to an extension of the resulting array if the carry continues beyond the length of both input arrays. The final step is to strip off any leading zeros to ensure the output conforms to the problem's no leading zero requirement. We then reverse the accumulated result to restore the array to the standard most significant bit to least significant bit format before returning.

Learn more about Math patterns.

Solution Approach

The solution utilizes a straightforward iterative approach, which is a common strategy when dealing with arithmetic problems involving positional number systems. The while loop constitutes the bulk of this approach, continuing as long as there are bits left to process in either arr1 or arr2, or there exists a carry-over c.

First, we initialize index variables i and j to point to the LSB (last element) of arr1 and arr2 respectively, and a c variable to keep track of the carry-over set initially to 0. The variable ans is an empty list to store the resulting sum bits in reverse order, due to the traversal from LSB to MSB.

Within the loop, we check if the index i or j is within the bounds of arr1 and arr2. If the index is out of bounds (i.e., < 0), we assume the value of that bit as 0. The a and b variables hold the current bit values from arr1 and arr2 or 0 if the index is beyond the array length.

Here comes the crucial part: summing up the current bits and the carry-over. We do this by adding a, b, and c and assigning the result to x. According to the base -2 rules, if x is 2 or larger, we know we've added two '1's and thus we adjust x by subtracting 2 and setting the carry to -1, because in base -2, "10" is -2 + 0 which simplifies to -2. Similarly, if x equals -1, we set x to 1, and increment the carry because in base -2, negative carry-over flips to positive in the next more significant bit.

We append the resulting bit x to the ans array, decrement i and j to move to the next more significant bit, and loop continues.

After exiting the loop, trailing zeros are removed from ans as they do not affect the value of the number and are not allowed in the output format according to the problem description. The only exception is if the entire number is 0, accounted for by the condition (while len(ans) > 1 and ans[-1] == 0).

Lastly, we reverse the ans list to change the order from LSB-MSB to the required MSB-LSB before returning it as the final sum.

This algorithm is efficient and only requires O(max(N,M)) time complexity where N and M are the lengths of arr1 and arr2 respectively, as we iterate through each bit once. The space complexity is also O(max(N,M)) which is required to store the output.

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 consider an example to illustrate the solution approach by manually adding two base -2 numbers represented by the arrays arr1 = [1, 0, 1] and arr2 = [1, 1, 1].

We will represent the numbers considering the least significant bit is on the left to match the reverse order we work with in the algorithm:

  arr1 = 1 0 1  (which is 1*-2^0 + 0*-2^1 + 1*-2^2 = 1 + 0 - 4 = -3 in decimal)
  arr2 = 1 1 1  (which is 1*-2^0 + 1*-2^1 + 1*-2^2 = 1 - 2 - 4 = -5 in decimal)

Now let's add them step by step as described in the solution approach:

Start with a while loop, indices i and j at the last elements, and carry c as 0.
At first iteration: a = arr1[i] which is 1, b = arr2[j] which is 1, c is 0. Sum x = a + b + c is 2. Following base -2 rules, we adjust x to 0 and set carry to -1.
Append x = 0 to ans and decrement i and j. ans = [0].
Next iteration: a = 0 from arr1, b = 1 from arr2, and carry c = -1. Sum is 0. As x is negative, we set x to 1 and add a positive carry of 1.
Append x = 1 to ans. Now, ans = [0, 1].
For the last bit (most significant), a = 1 from arr1, b = 1 from arr2, with a positive carry over. We sum up x = a + b + c which is 3, reduce it by 2 to get x = 1 and carry over -1.
We append x = 1 to ans. Now, ans = [0, 1, 1].
As there are no more elements in the arrays and the carry is -1, we add another iteration and subtract 2 again from the next significant bit, producing a 0 and carry -1.
Ans is updated to [0, 1, 1, 0].
Next, carry is -1, resulting in a bit of 1 with a carry of 1 (since -1 + 2 = 1 in base -2), producing a final array of [0, 1, 1, 0, 1].

Before returning the result, we must remove any leading zeros (keeping one if the number is zero) and then reverse the array for the proper base -2 representation:

  After removing leading zeros: [1, 1, 0, 1]
  After reversing: [1, 0, 1, 1]

The final ans array [1, 0, 1, 1] represents the sum of arr1 and arr2 in base -2, which is the number 4-1=3 in decimal. As one can check, -3 + (-5) = -8, and -8 in base -2 can be depicted as 1*-2^0 + 0*-2^1 + 1*-2^2 + 1*-2^3 = 1 + 0 - 4 + 8 = 5, which is the sum we expected.

Solution Implementation

1from typing import List
2
3class Solution:
4    def add_negabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
5        # Initialize pointers for arr1 and arr2
6        pointer_arr1, pointer_arr2 = len(arr1) - 1, len(arr2) - 1
7      
8        # Initialize carry to 0
9        carry = 0
10      
11        # Initialize result as an empty list
12        result = []
13      
14        # Loop until we have processed both arrays and any carry left
15        while pointer_arr1 >= 0 or pointer_arr2 >= 0 or carry:
16            # Get the current digits or 0 if we have passed the beginning
17            digit_arr1 = 0 if pointer_arr1 < 0 else arr1[pointer_arr1]
18            digit_arr2 = 0 if pointer_arr2 < 0 else arr2[pointer_arr2]
19          
20            # Calculate the new digit and adjust carry if necessary
21            digit_sum = digit_arr1 + digit_arr2 + carry
22            carry = 0  # reset carry
23            if digit_sum >= 2:
24                # When sum is 2 or more we have to subtract 2 and add -1 to carry for negabinary
25                digit_sum -= 2
26                carry -= 1
27            elif digit_sum == -1:
28                # When sum is -1 in negabinary, we have to add one to the digit and subtract from carry
29                digit_sum = 1
30                carry += 1
31          
32            # Append the result digit to the result list
33            result.append(digit_sum)
34          
35            # Move the pointers backwards
36            pointer_arr1, pointer_arr2 = pointer_arr1 - 1, pointer_arr2 - 1
37      
38        # Remove leading zeros from the result list except the last 0
39        while len(result) > 1 and result[-1] == 0:
40            result.pop()
41      
42        # Reverse the result to get the correct order since we added digits from the least significant
43        return result[::-1]
44

1class Solution {
2    public int[] addNegabinary(int[] arr1, int[] arr2) {
3        // Initialize indices for the last elements of arr1 and arr2
4        int i = arr1.length - 1;
5        int j = arr2.length - 1;
6
7        // Prepare a list to store the result
8        List<Integer> result = new ArrayList<>();
9
10        // 'carry' will keep track of the value to carry over to the next digit
11        for (int carry = 0; i >= 0 || j >= 0 || carry != 0; --i, --j) {
12            // Retrieve or default to zero if the index is less than zero
13            int digitArr1 = i < 0 ? 0 : arr1[i];
14            int digitArr2 = j < 0 ? 0 : arr2[j];
15
16            // Calculate the sum of the current digits and the carry
17            int sum = digitArr1 + digitArr2 + carry;
18            carry = 0; // Reset the carry
19
20            // Adjust the sum and carry for the negabinary system rules
21            if (sum >= 2) {
22                sum -= 2;
23                carry = -1; // In negabinary, carrying over '2' results in adding '-1' to the next more significant digit
24            } else if (sum == -1) {
25                sum = 1;
26                carry = 1; // In negabinary, having a sum of '-1' requires converting to '1' and carrying '1' over
27            }
28
29            // Add the calculated sum to the results list
30            result.add(sum);
31        }
32
33        // Remove leading zeros, except for the situation where the sum is exactly '0'
34        while (result.size() > 1 && result.get(result.size() - 1) == 0) {
35            result.remove(result.size() - 1);
36        }
37
38        // Since the current result is in reverse order, reverse it to obtain the correct order
39        Collections.reverse(result);
40
41        // Convert the list of Integers to a primitive int array
42        return result.stream().mapToInt(x -> x).toArray();
43    }
44}
45

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to add two negabinary numbers
7    std::vector<int> addNegabinary(std::vector<int>& arr1, std::vector<int>& arr2) {
8        int firstIndex = arr1.size() - 1; // Set the starting index for arr1
9        int secondIndex = arr2.size() - 1; // Set the starting index for arr2
10        std::vector<int> result; // Vector to store the result
11        int carry = 0; // Initialize the carry to 0
12
13        // Iterate while either arr1 or arr2 has digits left, or carry is non-zero
14        while (firstIndex >= 0 || secondIndex >= 0 || carry) {
15            int firstValue = firstIndex < 0 ? 0 : arr1[firstIndex]; // Get arr1 digit or 0 if index is negative
16            int secondValue = secondIndex < 0 ? 0 : arr2[secondIndex]; // Get arr2 digit or 0 if index is negative
17            int sum = firstValue + secondValue + carry; // Calculate the sum with carry
18          
19            // Reset the carry for the next calculation
20            carry = 0;
21
22            // Adjust the sum and carry for the next digit if necessary
23            if (sum >= 2) {
24                sum -= 2;
25                carry -= 1;
26            } else if (sum == -1) {
27                sum = 1;
28                carry += 1;
29            }
30          
31            // Add the calculated sum to the result
32            result.push_back(sum);
33          
34            // Decrement indices for next loop iteration
35            --firstIndex;
36            --secondIndex;
37        }
38
39        // Remove any leading zeros (but keep one zero if the result is zero)
40        while (result.size() > 1 && result.back() == 0) {
41            result.pop_back();
42        }
43      
44        // Reverse the result to get the correct ordering of digits
45        std::reverse(result.begin(), result.end());
46      
47        // Return the final result vector
48        return result;
49    }
50};
51

1function addNegabinary(arr1: number[], arr2: number[]): number[] {
2    let indexArr1 = arr1.length - 1; // Start from the end of the first array
3    let indexArr2 = arr2.length - 1; // Start from the end of the second array
4    const result: number[] = []; // Initialize the result array
5    let carry = 0; // Initialize the carry variable, which will store the carryover during addition
6
7    // Loop until both arrays are processed or there is a carry
8    while (indexArr1 >= 0 || indexArr2 >= 0 || carry) {
9        // Get the value from arr1 or 0 if indexArr1 is less than 0
10        const valArr1 = indexArr1 < 0 ? 0 : arr1[indexArr1];
11        // Get the value from arr2 or 0 if indexArr2 is less than 0
12        const valArr2 = indexArr2 < 0 ? 0 : arr2[indexArr2];
13
14        // Perform the addition with the values and the carry
15        let sum = valArr1 + valArr2 + carry;
16        carry = 0; // Reset carry to 0 for the next iteration
17
18        // Correct the sum and update the carry according to negabinary rules
19        if (sum >= 2) {
20            sum -= 2; // Subtract 2 when sum is 2 or more
21            carry = -1; // Set carry to -1 since we are in negabinary
22        } else if (sum === -1) {
23            sum = 1; // Set sum to 1 when it is -1
24            carry = 1; // Carry over 1
25        }
26      
27        // Prepend the calculated digit to the result array
28        result.unshift(sum);
29
30        // Move to the next digits
31        indexArr1--;
32        indexArr2--;
33    }
34
35    // Trimming leading zeros, except for the last 0 which represents the number zero
36    while (result.length > 1 && result[0] === 0) {
37        result.shift();
38    }
39
40    return result; // Return the computed negabinary number as an array of digits
41}
42

Time and Space Complexity

The code provided sums two negabinary numbers, represented as lists arr1 and arr2. The time complexity and space complexity of the code are as follows:

Time Complexity

The time complexity is governed by the length of the two input lists. Let n be the length of the longer list (arr1 or arr2). The main loop runs at most n times if one list is smaller than the other, and additional iterations occur for the carry c handling.

Therefore, the time complexity of the code is O(n), where n is the length of the longer input list. The while loops at the end trim leading zeros and take at most O(n) time in the worst case (when all bits are zeros except the first bit).

Space Complexity

The space complexity is determined by the additional space used to store the result. The ans list is built to store the sum of the two numbers, with space for an additional carry if necessary.

Thus, the space complexity of the code is also O(n), where n is the length of the longer input list. This accounts for the space needed for the ans list. It is essential to note that this does not include the space used to store the input lists themselves; it is the extra space required by the algorithm.

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

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know