Solution For Adding Two Negabinary Numbers
The problem “Adding Two Negabinary Numbers” on LeetCode is stated as follows:
Given two numbers arr1 and arr2 in negabinary representation, return the negabinary sum of the two numbers.
Negabinary is a base-2 system where the values of the digits can be -1, 0, or 1, instead of 0 or 1 in regular binary. For example, the negabinary representation of the number 3 is “11010”.
To solve this problem, we can follow the following steps:
Convert the two negabinary numbers to decimal. We can do this by iterating through each digit of the numbers, starting from the least significant digit, and multiplying the value of the digit (which can be -1, 0, or 1) by the corresponding power of 2 (which can be 2^n where n is the position of the digit, or -2^n if n is odd). We can then add the results to get the decimal equivalents of the two numbers.
Add the decimal equivalents of the two numbers obtained in step 1.
Convert the decimal sum obtained in step 2 to negabinary representation. To do this, we can use the “division by -2” algorithm, similar to the “division by 2” algorithm used for converting decimal to binary. We repeatedly divide the sum by -2 and keep track of the remainder at each step. If the remainder is negative, we add 2 to it and set the next dividend to be equal to the current dividend plus 1. We continue this process until the quotient is zero and we have obtained the negabinary representation of the sum.
Here is the Python implementation of the above algorithm:
“`
class Solution:
def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
# Convert the two negabinary numbers to decimal
num1 = sum(arr1[i] * (-2)i for i in range(len(arr1)))
num2 = sum(arr2[i] * (-2)i for i in range(len(arr2)))
# Add the decimal equivalents of the two numbers
decimal_sum = num1 + num2
# Convert the sum to negabinary representation
negabinary_sum = []
while decimal_sum != 0:
remainder = decimal_sum % -2
decimal_sum //= -2
if remainder < 0:
remainder += 2
decimal_sum += 1
negabinary_sum.append(remainder)
if not negabinary_sum:
return [0]
return negabinary_sum[::-1]
“`
In the above implementation, we first convert the two negabinary numbers to decimal using list comprehension. We then add the decimal equivalents of the two numbers to get the decimal sum. Finally, we convert the decimal sum to negabinary representation using a while loop that implements the “division by -2” algorithm. The resulting negabinary sum is returned.
Note that we have to check if the negabinary sum is empty and return [0] in that case. This happens if both arr1 and arr2 are [0]. We also reverse the negabinary sum using list slicing to get the correct order of digits.
Step by Step Implementation For Adding Two Negabinary Numbers
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Initialize carry to 0
int carry = 0;
// Initialize head of the resultant list to null
ListNode head = null;
// Initialize current node to head
ListNode curr = head;
// While both lists exist
while (l1 != null || l2 != null) {
// If one of the lists has ended, pad 0 to the other list
if (l1 == null) {
l1 = new ListNode(0);
}
if (l2 == null) {
l2 = new ListNode(0);
}
// Calculate sum of current digits and carry
int sum = l1.val + l2.val + carry;
// Calculate carry for next iteration
carry = (sum >= 2) ? -1 : 0;
// Get value of current digit
sum = (sum % 2 + 2) % 2;
// Create a new node with the sum as the data
ListNode newNode = new ListNode(sum);
// If this is the first node of the resultant list
if (head == null) {
// Set it as head
head = newNode;
// Set current node as head
curr = head;
} else {
// Else, connect it to the tail
curr.next = newNode;
// Set current node as the new node
curr = curr.next;
}
// Move to the next nodes of the input lists
l1 = l1.next;
l2 = l2.next;
}
// If carry is left over, add a new node with carry as the data
if (carry == -1) {
curr.next = new ListNode(-1);
}
// Return head of the resultant list
return head;
}
}def addNegabinary(a, b): # initialize result result = 0 # initialize base value base = 1 # traverse both arrays from right to left i, j = len(a) - 1, len(b) - 1 while i >= 0 or j >= 0: # find sum of current digits and carry sum = 0 if i >= 0: sum += a[i] i -= 1 if j >= 0: sum += b[j] j -= 1 # if current digit sum is 1 or 3, add 1 to result if sum == 1 or sum == 3: result += base # increment base by 2 base = base * 2 # return result return result
/**
* @param {number[]} arr1
* @param {number[]} arr2
* @return {number[]}
*/
var addNegabinary = function(arr1, arr2) {
};class Solution {
public:
vector addNegabinary(vector& arr1, vector& arr2) {
int i = arr1.size() - 1, j = arr2.size() - 1, carry = 0;
vector result;
while (i >= 0 || j >= 0 || carry) {
int sum = (i >= 0 ? arr1[i--] : 0) + (j >= 0 ? arr2[j--] : 0) + carry;
result.push_back(sum & 1);
carry = -(sum >> 1);
}
while (result.size() > 1 && result.back() == 0)
result.pop_back();
reverse(result.begin(), result.end());
return result;
}
}; public class Solution {
public int[] AddNegabinary(int[] arr1, int[] arr2) {
// Your code here
}
}