# Leetcode 67. Add Binary
###### tags: `leetcode` `daily` `binary string`

[題目連結](https://leetcode.com/problems/add-binary/description/)

# Method
:::info
:bulb: **作法講解**:
we can scan each character from last character to first character,
we use var over to record last character is overflow,
overflow it means last character a[i] and b[i] is 1.
current value is a[i] + b[i] + overflow
for each character, we put the result character to back the output string,
after finish scan all character, reverse the output string.
:::

TC: O(N) SC: O(N)
:::spoiler 完整程式碼

class Solution {
public:
    string addBinary(string a, string b) {
        int an = a.size();
        int bn = b.size();
        int flag = 0;
        int idx = 0;
        string output = "";
        
        while((idx < an) || (idx < bn)) {
            int av = (idx < an) ? (a[an - idx - 1] - '0') : 0;
            int bv = (idx < bn) ? (b[bn - idx - 1] - '0') : 0;
            int v = flag + av + bv;
            output += ('0' + (v % 2));
            flag = (v > 1);
            idx++;
        }

        if(flag) {
            output += '1';
        }

        reverse(output.begin(), output.end());
        return output;
    }
};

:::