# Leetcode 67 add binary string
<ol>
<li>二進位加法</li>
<li>% 用來取餘數</li>
<li>// 用來取整數作為進位</li>
</ol>

My Solution 時間複雜 O(max(len(a), len(b)))
---

def addBinary(self, a, b):
    # 輸入二進位兩個數字，要你做加法
    # a,b % 10 餘數為10 or 1
    # 如果不是餘10 or 1 回傳空值
    if not (a%10 == 0 or a%10 == 1) /
    and (b % 10 == 0 or b % 10 == 1):
        return ""
    # 如果兩個都為0
    if int(a)==0 and int(b)==0:
        return "0"
    # str(a) 會是反過來
    list_a = [i for i in a] # 剛開始讀取
    list_b = [j for j in b] 
    list_a.reverse() # python內建陣列反轉
    # list_a = [list_a[i] for i in range(len(list_a)-1,-1,-1)] #反過來
    list_b = [list_b[i] for i in range(len(list_b)-1,-1,-1)] #反過來
    a_num = 0 ; b_num=0
    # 將反轉後的陣列利用enumerate換成10進位
    for index,num in enumerate(list_a):
        a_num += 2**(index)*int(num)
    for index,num in enumerate(list_b):
        b_num += 2**(index)*int(num)
    sum = a_num+b_num ; x = 0
    # 尋找最接近的次方
    while (2**x <= sum):
        x+=1
    x-=1 ; ans =""
    # 從最大次方開始作，%取餘數 //取整數
    for i in range(x,-1,-1):
        ans += str(sum // (2**i))
        sum %= (2**i)
    return ans  

Best Solution 我也有想出來更好的算法 DP解
時間 O(max(len(a), len(b)))
---

def addBinary(self, a, b):
    list_a = [i for i in str(a)]
    list_b = [i for i in str(b)]
    i = len(list_a)-1; j= len(list_b)-1; 
    plus = 0 ; ans = ''
    while i>=0 or j>=0 or plus==1:
        if i>=0:
            # 從最右邊開始作相加
            plus+=int(list_a[i]) 
        if j>=0:
            # 從最右邊開始作相加
            plus+=int(list_b[j]) 
        # 前面位數為大的，取餘數作輸出
        # ex:3%2=1，因此要填入1，新加入字串在左邊
        ans = str(plus % 2) +ans 
        # plus 3//2=1 代表要進位，把plus帶到下一個位數
        # 通常 plus 只會有 3//2 or 2//2
        i, j, plus = i-1, j-1, plus//2 
    return ans

###### tags: `LeetCode` `binary add`