For example,
a =
"11"b =
"1"Return
"100".
Similar to the problem Plus One. Time complexity is O(n) and we ignore the required return value the space complexity is O(1).
public String addBinary(String a, String b) {
if(a.length() < b.length()) {
return addBinary(b, a);
}
StringBuffer sb = new StringBuffer();
int ind1 = a.length() - 1, ind2 = b.length() - 1;
int carry = 0;
while(ind2 >= 0) {
int num1 = a.charAt(ind1) - '0';
int num2 = b.charAt(ind2) - '0';
int res = num1 + num2 + carry;
carry = res / 2;
res = res % 2;
ind1--; ind2--;
sb.append(res);
}
while(ind1 >= 0) {
int num1 = a.charAt(ind1) - '0';
int res = num1 + carry;
carry = res / 2;
res = res % 2;
ind1--;
sb.append(res);
}
if(carry != 0)
sb.append(carry);
sb = sb.reverse();
return sb.toString();
}
没有评论:
发表评论