# LeetCode Easy 67. Add Binary

tags: leetcode

問題

• Explore
• Problems

アイデア

｢2つの二進数の文字列を与えられたとき，それらの和を二進数で返せ｣という問題です．

普段する計算と同じように文字列の小さい桁から見ていきます．

解法

• a，bの文字列で現在見ている箇所を指すための変数a_posとb_posを用意します．
• これらが0以上のときはその箇所の値をcarryという変数に加え，桁を上げます．
  • 2進数なのでcarryの1桁目(2で割った余り)をresの先頭に加えます．
  • そして，2で割った商を代入します．

計算量

文字列a，bの大きさをそれぞれN，Mとします．

• 時間計算量
  • aとbを走査するので$O(N + M)$
• 空間計算量
  • 答えとなる文字列を格納するのに$O(NM)$

Python

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        a_pos, b_pos = len(a)-1, len(b)-1
        res = ""
        carry = 0

        while a_pos >= 0 or b_pos >= 0 or carry:
            if a_pos >= 0:
                carry += int(a[a_pos])
                a_pos -= 1
            if b_pos >= 0:
                carry += int(b[b_pos])
                b_pos -= 1
            res = str(carry % 2) + res
            carry //= 2
        return res