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.
What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Solution 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.
Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?
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:
1 arr1 = 1 0 1 (which is 1*-2^0 + 0*-2^1 + 1*-2^2 = 1 + 0 - 4 = -3 in decimal) 2 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
whileloop, indicesiandjat the last elements, and carrycas 0. - At first iteration:
a = arr1[i]which is 1,b = arr2[j]which is 1,cis 0. Sumx = a + b + cis 2. Following base -2 rules, we adjustxto0and set carry to-1. - Append
x = 0toansand decrementiandj.ans = [0]. - Next iteration:
a = 0fromarr1,b = 1fromarr2, and carryc = -1. Sum is0. Asxis negative, we setxto1and add a positive carry of1. - Append
x = 1toans. Now,ans = [0, 1]. - For the last bit (most significant),
a = 1fromarr1,b = 1fromarr2, with a positive carry over. We sum upx = a + b + cwhich is 3, reduce it by 2 to getx = 1and carry over-1. - We append
x = 1toans. Now,ans = [0, 1, 1]. - As there are no more elements in the arrays and the carry is
-1, we add another iteration and subtract2again from the next significant bit, producing a0and carry-1. Ansis updated to[0, 1, 1, 0].- Next, carry is
-1, resulting in a bit of1with a carry of1(since-1 + 2 = 1in 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:
1 After removing leading zeros: [1, 1, 0, 1] 2 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]
441class 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}
451#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};
511function 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}
42Which one best describes the time complexity of the following code?
1int factorial(int n) {
2 if (n < 0) {
3 return -1;
4 } else if (n == 0) {
5 return 1;
6 } else {
7 return n * factorial(n - 1);
8 }
9}
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.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching 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.