class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        char carry = '0';
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0)
        {
            char digit1 = i >= 0 ? a.charAt(i) : '0';
            char digit2 = j >= 0 ? b.charAt(j) : '0';
            char result = '0';

            if ((digit1 == '0' && digit2 == '0' && carry == '0') || (digit1 == '1' && digit2 == '0' && carry == '1'))
            {
                result = '0';
            }
            else if (digit1 == '0' && digit2 == '0' && carry == '1')
            {
                result = '1';
                carry = '0';
            }
            else if ((digit1 == '0' && digit2 == '1' && carry == '0') || (digit1 == '1' && digit2 == '0' && carry == '0') || (digit1 == '1' && digit2 == '1' && carry == '1'))
            {
                result = '1';
            }
            else if ((digit1 == '0' && digit2 == '1' && carry == '1') || (digit1 == '1' && digit2 == '1' && carry == '0'))
            {
                result = '0';
                carry = '1';
            }

            sb.insert(0, result);
            i--;
            j--;
        }

        if (carry == '1')
        {
            sb.insert(0, carry);
        }

        return sb.toString();
    }
  
    // public String addBinary(String a, String b) {
    //     int i = a.length() - 1;
    //     int j = b.length() - 1;
    //     char carry = '0';
    //     StringBuilder sb = new StringBuilder();

    //     while (i >= 0 || j >= 0)
    //     {
    //         char digit1 = i >= 0 ? a.charAt(i) : '0';
    //         char digit2 = j >= 0 ? b.charAt(j) : '0';
    //         char result = '0';

    //         if (digit1 == '0' && digit2 == '0' && carry == '0')
    //         {
    //             result = '0';
    //             carry = '0';
    //         }
    //         else if (digit1 == '0' && digit2 == '0' && carry == '1')
    //         {
    //             result = '1';
    //             carry = '0';
    //         }
    //         else if (digit1 == '0' && digit2 == '1' && carry == '0')
    //         {
    //             result = '1';
    //             carry = '0';
    //         }
    //         else if (digit1 == '0' && digit2 == '1' && carry == '1')
    //         {
    //             result = '0';
    //             carry = '1';
    //         }
    //         else if (digit1 == '1' && digit2 == '0' && carry == '0')
    //         {
    //             result = '1';
    //             carry = '0';
    //         }
    //         else if (digit1 == '1' && digit2 == '0' && carry == '1')
    //         {
    //             result = '0';
    //             carry = '1';
    //         }
    //         else if (digit1 == '1' && digit2 == '1' && carry == '0')
    //         {
    //             result = '0';
    //             carry = '1';
    //         }
    //         else if (digit1 == '1' && digit2 == '1' && carry == '1')
    //         {
    //             result = '1';
    //             carry = '1';
    //         }

    //         sb.insert(0, result);
    //     }

    //     if (carry == '1')
    //     {
    //         sb.insert(0, carry);
    //     }

    //     return sb.toString();
    // }
}