[LeetCode] 67. Add Binary

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

For example,
a = "11"
b = "1"
Return "100".

Thought process:

Add from right to left. Keep track of carry. Loop until both pointers and carry become 0.

Solution 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public String addBinary(String a, String b) { int i = a.length() - 1; int j = b.length() - 1; int carry = 0; String result = ""; while (i >= 0 || j >= 0 || carry > 0) { int digit1 = i >= 0 ? a.charAt(i) - '0' : 0; int digit2 = j >= 0 ? b.charAt(j) - '0' : 0; int sum = carry + digit1 + digit2; carry = sum / 2; result = sum % 2 + result; i--; j--; } return result; } }

Solution 2 (StringBuilder):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public String addBinary(String a, String b) { StringBuilder sb = new StringBuilder(); int carry = 0; int i = a.length() - 1; int j = b.length() - 1; while (i >= 0 || j >= 0 || carry > 0) { int digit1 = i >= 0 ? a.charAt(i) - '0' : 0; int digit2 = j >= 0 ? b.charAt(j) - '0' : 0; int sum = digit1 + digit2 + carry; carry = sum / 2; sb.append(sum % 2); i--; j--; } return sb.reverse().toString(); } }

Time complexity: O(a + b).