Add Binary

Math

EasyLeetCode #67

20 min

Problem Statement

Given two binary strings a and b, return their sum as a binary string.

Example

Example 1:

Input: a = "11", b = "1"

Output: "100"

Solution (Math)

We can simulate binary addition from right to left, keeping track of a carry.

Algorithm Steps

Initialize an empty result string and a carry of 0.
Iterate from the end of both strings.
In each step, add the digits from both strings (if they exist) and the carry.
The new digit for the result is the sum modulo 2.
The new carry is the sum divided by 2.
Prepend the new digit to the result string.
After the loop, if there's a remaining carry, prepend it to the result.

String a:

String b:

1010

1011

Carry

Result

Start with a = 1010, b = 1011, carry = 0.

Add Binary Solution


class Solution:
    def addBinary(self, a: str, b: str) -> str:
        res = ""
        carry = 0
        
        a, b = a[::-1], b[::-1]
        
        for i in range(max(len(a), len(b))):
            digitA = int(a[i]) if i < len(a) else 0
            digitB = int(b[i]) if i < len(b) else 0
            
            total = digitA + digitB + carry
            char = str(total % 2)
            res = char + res
            carry = total // 2
            
        if carry:
            res = "1" + res
        return res