Problem
Given two binary strings, return their sum in binary string.
Example 1:
Input: a = "11", b = "11"
Output: "110"
Example 2:
Input: a = "1010", b = "101"
Output: "1111"
Solution
With Integer.parseInt(x, 2) and Integer.toBinaryString, we can get the answer with 2 lines. The time complexity depends on the jvm implementation, which should be O(M+N). The space complexity is O(max(N,M)), the space complexity is O(max(N,M)) to keep the answer.
We can also get the same result with binary manipulation. The time complexity is O(M+N), the space complexity is O(max(N,M)) to keep the answer.
public class BinarySum {
public static String add(String a, String b) {
return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
}
public static String bitAdd(String a, String b) {
int ab = Integer.parseInt(a, 2);
int bb = Integer.parseInt(b, 2);
int sumWithoutCarry = ab ^ bb;
int carry = (ab & bb)<<1;
while(carry != 0) {
sumWithoutCarry = ab ^ bb;
carry = (ab & bb)<<1;
ab = sumWithoutCarry;
bb = carry;
}
return Integer.toBinaryString(sumWithoutCarry);
}
public static void main(String...args) {
System.out.println(add("11", "11"));
System.out.println(add("1010", "101"));
System.out.println(bitAdd("11", "11"));
System.out.println(bitAdd("1010", "101"));
}
}
public static String add(String a, String b) {
return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
}
public static String bitAdd(String a, String b) {
int ab = Integer.parseInt(a, 2);
int bb = Integer.parseInt(b, 2);
int sumWithoutCarry = ab ^ bb;
int carry = (ab & bb)<<1;
while(carry != 0) {
sumWithoutCarry = ab ^ bb;
carry = (ab & bb)<<1;
ab = sumWithoutCarry;
bb = carry;
}
return Integer.toBinaryString(sumWithoutCarry);
}
public static void main(String...args) {
System.out.println(add("11", "11"));
System.out.println(add("1010", "101"));
System.out.println(bitAdd("11", "11"));
System.out.println(bitAdd("1010", "101"));
}
}
The time complexity is O(M+N), the space complexity is O(max(N,M)).
The best performance algorithm, surprisingly, is the old good bit by bit add with carry bit, which has time complexity O(max(M, N) and space complexity O(max(M, N)).
The best performance algorithm, surprisingly, is the old good bit by bit add with carry bit, which has time complexity O(max(M, N) and space complexity O(max(M, N)).
