Bit Manipulation Flashcards

1
Q

67 - Add Binary
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”

Time Complexity : - O(n) where n is length of longest of two strings.
Space Complexity:- O(n) where n is length of longest of two strings.

A

Take Aways:-
1. Use while Loop to handle unequal lengths of two strings and add digit from string only if its index is valid.
2. Append sum%2 directly instead of appending 0 or 1 when sum is 2 or 3;
Code:-
public String addBinary(String a, String b) {
StringBuilder result=new StringBuilder();
int i=a.length()-1;int j=b.length()-1;
int carry=0;int sum=0;
while(i>=0||j>=0){
sum=carry;
if(i>=0) sum+=a.charAt(i) -‘0’;
if(j>=0) sum+=b.charAt(j) -‘0’;
i–;j–;
carry=sum>1?1:0;
result.insert(0,sum%2);
}
if(carry>0){
result.insert(0,carry);
}
return result.toString();
}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly