1073. Adding Two Negabinary Numbers LeetCode Solution

In this guide, you will get 1073. Adding Two Negabinary Numbers LeetCode Solution with the best time and space complexity. The solution to Adding Two Negabinary Numbers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Adding Two Negabinary Numbers solution in C++
  4. Adding Two Negabinary Numbers solution in Java
  5. Adding Two Negabinary Numbers solution in Python
  6. Additional Resources
1073. Adding Two Negabinary Numbers LeetCode Solution image

Problem Statement of Adding Two Negabinary Numbers

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.
Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array, format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.
Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Example 1:

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Example 2:

Input: arr1 = [0], arr2 = [0]
Output: [0]

Example 3:

Input: arr1 = [0], arr2 = [1]
Output: [1]

Constraints:

1 <= arr1.length, arr2.length <= 1000
arr1[i] and arr2[i] are 0 or 1
arr1 and arr2 have no leading zeros

See also  61. Rotate List LeetCode Solution

Complexity Analysis

  • Time Complexity:
  • Space Complexity:

1073. Adding Two Negabinary Numbers LeetCode Solution in C++

class Solution {
 public:
  vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
    deque<int> ans;
    int carry = 0;
    int i = arr1.size() - 1;
    int j = arr2.size() - 1;

    while (carry != 0 || i >= 0 || j >= 0) {
      if (i >= 0)
        carry += arr1[i--];
      if (j >= 0)
        carry += arr2[j--];
      ans.push_front(carry & 1);
      carry = -(carry >> 1);
    }

    while (ans.size() > 1 && ans.front() == 0)
      ans.pop_front();

    return {ans.begin(), ans.end()};
  }
};
/* code provided by PROGIEZ */

1073. Adding Two Negabinary Numbers LeetCode Solution in Java

class Solution {
  public int[] addNegabinary(int[] arr1, int[] arr2) {
    Deque<Integer> ans = new ArrayDeque<>();
    int carry = 0;
    int i = arr1.length - 1;
    int j = arr2.length - 1;

    while (carry != 0 || i >= 0 || j >= 0) {
      if (i >= 0)
        carry += arr1[i--];
      if (j >= 0)
        carry += arr2[j--];
      ans.addFirst(carry & 1);
      carry = -(carry >> 1);
    }

    while (ans.size() > 1 && ans.getFirst() == 0)
      ans.pollFirst();

    return ans.stream().mapToInt(Integer::intValue).toArray();
  }
}
// code provided by PROGIEZ

1073. Adding Two Negabinary Numbers LeetCode Solution in Python

class Solution:
  def addNegabinary(self, arr1: list[int], arr2: list[int]) -> list[int]:
    ans = []
    carry = 0

    while carry != 0 or arr1 or arr2:
      if arr1:
        carry += arr1.pop()
      if arr2:
        carry += arr2.pop()
      ans.append(carry & 1)
      carry = -(carry >> 1)

    while len(ans) > 1 and ans[-1] == 0:
      ans.pop()

    return ans[::-1]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: