DEV Community

Cover image for Add Binary
FakeStandard
FakeStandard

Posted on

Add Binary

#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"
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: a = "1010", b = "1011"
Output: "10101"
Enter fullscreen mode Exit fullscreen mode

Explanation

給定兩個二進位制的字串 ab ,將他們相加並返回二進位制的結果

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);
}
Enter fullscreen mode Exit fullscreen mode

測試沒問題直接提交,得到與上一題 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();
}
Enter fullscreen mode Exit fullscreen mode

Reference

LeetCode Solution

GitHub Repository


Thanks for reading the article 🌷 🌻 🌼

If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub
or buy me a coffee ⬇️ I'd appreciate it.

Buy-me-a-coffee


Top comments (0)