67. Add Binary

• python3

Problem

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

Example 1:

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

Example 2:

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

Constraints:

• 1 <= a.length, b.length <= 104
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

Pseudocode

set two pointers(aP, bP) for a, b
set stack for carry

while aP >= 0 or bP > = 0:
	sum = stack
    if aP >=0 -> sum+= a[aP]
    if bp >= 0 -> sum+= b[bP]
    aP, bP -= 1
	if sum >= 2 -> stack = 1
    else -> stack = 0
    result += str(sum%2)
   
if stack != 0 -> result += str(stack)

return reverse of result

Code

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        
        result = ""
        aPointer = len(a) - 1
        bPointer = len(b) - 1
        stack = 0

        while aPointer >= 0 or bPointer >= 0:
            sum = stack
            if aPointer >=0:
                sum += ord(a[aPointer]) - ord('0')
            if bPointer >=0:
                sum += ord(b[bPointer]) - ord('0')
            aPointer -= 1
            bPointer -= 1
            if sum >= 2:
                stack = 1
            else:
                stack = 0
            result += str(sum%2)
        
        if stack != 0:
            result += str(stack)

        return result[::-1] #print reverse

Result

• Time Complexity: O(n)
• Space Complexity : O(n)