Add Binary

#algorithms #csharp #leetcode #easy

#67.Add Binary

Problem statement

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"

Explanation

給定兩個二進位制的字串 a 和 b ，將他們相加並返回二進位制的結果

Solution

將兩字串轉換成十進位，接著兩者相加得到總和，總和在轉換成二進位得到答案

public string AddBinary(string a, string b)
{
    var x = Convert.ToInt32(a, 2);
    var y = Convert.ToInt32(b, 2);

    var res = x + y;

    return Convert.ToString(res, 2);
}

測試沒問題直接提交，得到與上一題 Plus One 相同的錯誤，果然沒這麼簡單！於是我尋思著上一題的解法，這題用相同邏輯應該不會有問題，我朝著這個方向前進，建立一個 carry 變數來紀錄是否進位，以及 sb 來合併每次執行結果，上一題 Plus One 是對一個數加一，這題是兩個數相加，沒什麼太難的問題，只是有些小細節要注意

public string AddBinary(string a, string b)
{
    // 將 a,b 補 0 直到相同長度
    int maxLen = a.Length > b.Length ? a.Length : b.Length;
    a = a.PadLeft(maxLen, '0');
    b = b.PadLeft(maxLen, '0');

    // true 表示進位, false 則無
    bool carry = false;
    StringBuilder sb = new StringBuilder();

    int add;

    maxLen--;

    // 依據各種狀況進行相加
    while (maxLen > -1)
    {
        add = a[maxLen] + b[maxLen];

        if (add == 98) // a+b=2
        {
            if (carry)
                sb.Insert(0, '1');
            else
            {
                sb.Insert(0, '0');
                carry = true;
            }
        }
        else if (add == 97) // a+b=1
        {
            if (carry)
                sb.Insert(0, '0');
            else
                sb.Insert(0, '1');
        }
        else // a+b=0
        {
            if (carry)
            {
                sb.Insert(0, '1');
                carry = false;
            }
            else
                sb.Insert(0, '0');
        }

        maxLen--;
    }

    if (carry) sb.Insert(0, '1');

    return sb.ToString();
}