Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0067 - Add Binary
    0067 - Add Binary
    0067 - Add Binary
    0067 - Add Binary

    0067 - Add Binary

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/add-binary/

    Solution 1 - Iterative Bit-by-Bit Addition

    Traverse both binary strings from right to left, adding corresponding digits along with any carry. Build the result string by prepending each computed bit. Continue until both strings are exhausted and no carry remains.

    TimeComplexity:O(max(m,n))TimeComplexity: O(max(m, n))TimeComplexity:O(max(m,n))
    SpaceComplexity:O(max(m,n))SpaceComplexity: O(max(m, n))SpaceComplexity:O(max(m,n))

    Solution 2 - Stack-Based Addition with Pop

    Use lists (as stacks) from the input strings and pop digits from the end of each. Sum digits with carry, append the result bit, and reverse at the end.

    TimeComplexity:O(max(m,n))TimeComplexity: O(max(m, n))TimeComplexity:O(max(m,n))
    SpaceComplexity:O(max(m,n))SpaceComplexity: O(max(m, n))SpaceComplexity:O(max(m,n))
    """ 0067.1 - Add Binary - Solution 1 - Iterative Bit-by-Bit Addition """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def addBinary(self, a: str, b: str) -> str:
        """Add Binary Function"""
        result = []
        carry = 0
        i, j = len(a) - 1, len(b) - 1

        while i >= 0 or j >= 0 or carry:
            total = carry
            if i >= 0:
                total += int(a[i])
                i -= 1
            if j >= 0:
                total += int(b[j])
                j -= 1
            result.append(str(total % 2))
            carry = total // 2

        return ''.join(reversed(result))


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().addBinary("11", "1"))        # "100"
    print(Solution().addBinary("1010", "1011"))   # "10101"


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0067.2 - Add Binary - Solution 2 - Stack-Based Addition with Pop """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def addBinary(self, a: str, b: str) -> str:
        """Add Binary Function"""
        a, b = list(a), list(b)
        carry = 0
        result = ""

        while a or b or carry:
            if a:
                carry += int(a.pop())
            if b:
                carry += int(b.pop())
            result = str(carry % 2) + result
            carry //= 2

        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().addBinary("11", "1"))        # "100"
    print(Solution().addBinary("1010", "1011"))   # "10101"


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()