Tuesday, February 14, 2023

[LeetCode] Add Binary

Problem: Given two binary strings a and b, return their sum as a binary string.

Example:

Input: a = "11", b = "1"
Output: "100"
Input: a = "1010", b = "1011"
Output: "10101"


Approach: Nothing much to discuss here. Its an easy problem to solve. Just look at the implementation to understand the approach.


Implementation in C#:

    public string AddBinary(string a, string b)
    {
        int lenA = a.Length;
        int lenB = b.Length;
        int maxLen = Math.Max(lenA, lenB);
        char[] res = new char[maxLen];
        int i = lenA - 1, j = lenB - 1;
        int k = maxLen - 1;
        int carry = 0;  
        while(i >= 0 && j >= 0)
        {
            char add = '0';
            if (a[i] == '1' && b[j] == '1')
            {
                add ='0';
                if (carry == 1)
                {
                    add = '1';
                }
                carry = 1;
            }
            else if (a[i] == '0' && b[j] == '0')
            {
                add = '0';
                if (carry == 1)
                {
                    add = '1';
                }
                carry = 0;
            }
            else
            {
                add = '1';  
                if (carry == 1)
                {
                    add = '0';
                    carry = 1;
                }
                else
                {
                    carry = 0;
                }
            }
            res[k--] = add;
            --i;
            --j;
        }
        if (i >= 0)
        {
            this.HandleSingleNum(a, i, res, k, ref carry);
        }
        if (j >= 0)
        {
            this.HandleSingleNum(b, j, res, k, ref carry);
        }
        string result = carry == 1 ?
                        "1" + new string(res) :
                        new string(res);
        return result;
    }

    private void HandleSingleNum(
        string num,
        int numIndex,
        char[] result,
        int resIndex,
        ref int carry)
    {
        while(numIndex >= 0)
        {
            if (num[numIndex] == '0')
            {
                if (carry == 1)
                {
                    result[resIndex--] = '1';
                }
                else
                {
                    result[resIndex--] = '0';
                }
                carry = 0;
            }
            else
            {
                if (carry == 1)
                {
                    result[resIndex--] = '0';
                    carry = 1;
                }
                else
                {
                    result[resIndex--] = '1';
                    carry = 0;
                }
            }
            --numIndex;
        }
    }

Complexity: O(n) where n is max of length of a and length of b.

No comments:

Post a Comment