Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1148. Adding Two Negabinary Numbers

My accepted Python solution to LeetCode problem 1148, Adding Two Negabinary Numbers, running in 1ms.

  • Difficulty: Medium
  • Python
  • Runtime 1ms
  • Memory 17.3MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 1ms, memory 17.3MB, accepted 2026-01-02.

python
class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        result = []
        carry = 0
        i, j = len(arr1) - 1, len(arr2) - 1
        
        while i >= 0 or j >= 0 or carry:
            if i >= 0:
                carry += arr1[i]
                i -= 1
            if j >= 0:
                carry += arr2[j]
                j -= 1
            
            # In base -2, we have: carry = digit + (-2) * new_carry
            # digit should be 0 or 1
            result.append(carry & 1)  # carry % 2
            carry = -(carry >> 1)     # -carry // 2
        
        # Remove leading zeros
        while len(result) > 1 and result[-1] == 0:
            result.pop()
        
        return result[::-1]

Source