67. Add Binary.md

67. Add Binary

---

leetcode-cn Daily Challenge on June 23th, 2020.

leetcode Daily Challenge on July 19th, 2020.

---

Difficulty : Easy

Related Topics : Math、String

---

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Constraints:

• Each string consists only of '0' or '1' characters.
• 1 <= a.length, b.length <= 10^4
• Each string is either "0" or doesn't contain any leading zero.

---

Solution

• mine
  • Java
    • Runtime: 1 ms, faster than 100.00%, Memory Usage: 38.3 MB, less than 64.54% of Java online submissions

      // O(N)time O(N)space
      // N = Math.max(a.length(),b.length())
      public String addBinary(String a, String b) {
          char[] arrA = a.toCharArray();
          char[] arrB = b.toCharArray();
          if (a.length() < b.length()) {
              char[] temp = arrA;
              arrA = arrB;
              arrB = temp;
          }
          int lenA = arrA.length, lenB = arrB.length;
          int count = 0;
          for (int i = 0; i < lenA; i++) {
              int t;
              if (i < lenB) {
                  t = count + arrA[lenA - 1 - i] - '0' + arrB[lenB - 1 - i] - '0';
              } else {
                  t = count + arrA[lenA - 1 - i] - '0';
              }
              arrA[lenA - 1 - i] = (char) ('0' + t % 2);
              count = t / 2;
          }
          if (count == 0) {
              return new String(arrA);
          }
          char[] arr = new char[arrA.length + 1];
          arr[0] = (char) (count + '0');
          System.arraycopy(arrA, 0, arr, 1, arrA.length);
          return new String(arr);
      }
      

---

• the most votes
  • Runtime: 1 ms, faster than 100.00%, Memory Usage: 37.9 MB, less than 90.72% of Java online submissions

    // O(N)time O(N)space
    // N = Math.max(a.length(),b.length())
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() -1, carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (j >= 0) sum += b.charAt(j--) - '0';
            if (i >= 0) sum += a.charAt(i--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
    

---