67. Add Binary

Problem Statement

link: link: LeetCode.cn LeetCode

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

Example:

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

Input: a = "1010", b = "1011" Output: "10101"

Solution Approach

The solution involves simulating the process of binary addition bit-by-bit, considering the carry from one bit to the next.

Algorithm

1. Padding: Equalize the lengths of both binary strings by adding leading zeros to the shorter one.
2. Bitwise Addition: Iterate from rightmost bit to leftmost, adding corresponding bits from both strings and any carry from the previous step.
3. Handle Final Carry: If there’s a remaining carry after all bits are processed, prepend “1” to the result.

Implement

    class Solution:
    def addBinary(self, a: str, b: str) -> str:
      def add(x, y, carry):
          s = x + y + carry
          return(s // 2,s % 2)
      ml = max(len(a), len(b))
      a = a.rjust(ml, '0')
      b = b.rjust(ml, '0')
      res = ''
      carry = 0
      for i in range(ml - 1, -1, -1):
          carry, n = add(int(a[i]), int(b[i]), carry)
          res = str(n) + res
      return '1' + res if carry else res
      
      

    
    

Twitter  facebook  Email