using System;

​

public class Program

{

    /*

     *  Two binary numbers as strings, add the numbers together and return

     *  the result as a binary string.

     *

     *    10 + 1 => 11

     *    1001 + 1 => 1010

     *    1101 + 100 => 10001

     *    10101010 + 11001100 => 101110110

     */

    public static void Main()

    {

        Console.WriteLine(AddBinaryNumbers("10","1"));

        Console.WriteLine(AddBinaryNumbers("1001","1"));

        Console.WriteLine(AddBinaryNumbers("1101", "100"));

        Console.WriteLine(AddBinaryNumbers("10101010", "11001100"));

    }

    public static string AddBinaryNumbers(string a, string b)

    {

        string result = "";

​

        // Initialize digit sum 

        int s = 0;

​

        // Traverse both strings starting from last characters 

        int i = a.Length - 1;

        int j = b.Length - 1;

​

        // O(n) + O(n) -> O(2n)

        while (i >= 0 || j >= 0 || s == 1)

        {

            // Padding cases, so if there is '1' + '101' it actually will be '001' + '101'

            // Note: '1'-'0' converts char back to its numeric value

            s += (i >= 0 ? a[i] - '0' : 0); // Add character "a[i]" as a numeric value to s.

            s += (j >= 0 ? b[j] - '0' : 0); // Add character "b[i]" as a numeric value to s.

​

            // numeric + '0' converts it to corresponding char again

            // If current digit sum (s) is 1 or 3, add '1' to result, otherwise add a '0' char

            result = (char)(s % 2 + '0') + result;

​

            // Compute carry over.

            s /= 2;

​

            // Decrement our index. 

            i--; 

            j--;

        }

        return result;

    }

}