hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Add binary strings
Problem: 67. Add binary strings
Problem Link:
Companies Asked: Uber, Adobe, Amazon, Google, Facebook, Snapchat, Microsoft
Approach:
The first step is if both the strings are not of equal length then, pad the string of smaller length with leading 0s.
Initiate a variable to store the carry status.
Now sum up each ith digit. And also sum the carry with it.
Concatenate the result in the resultant string.
Return the resultant string.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(N)
Code [C++]
class Solution {
public:
string addBinary(string a, string b) {
int n = b.size(), m = a.size();
if(n > m){
swap(a, b);
swap(n, m);
}
string zeroes = "";
for(int i=n; i<m; i++) zeroes += "0";
b = zeroes + b;
// cout<<"b "<<b<<endl;
string ans = "";
bool carry = false;
for(int i=m-1; i>=0; i--){
if(a[i] == '0' && b[i] == '0' && carry){
ans += "1"; carry = false;
}
else if(a[i] == '0' && b[i] == '0' && !carry){
ans += "0"; carry = false;
}
else if(a[i] == '0' && b[i] == '1' && carry){
ans += "0"; carry = true;
}
else if(a[i] == '0' && b[i] == '1' && !carry){
ans += "1"; carry = false;
}
else if(a[i] == '1' && b[i] == '0' && carry){
ans += "0"; carry = true;
}
else if(a[i] == '1' && b[i] == '0' && !carry){
ans += "1"; carry = false;
}
else if(a[i] == '1' && b[i] == '1' && carry){
ans += "1"; carry = true;
}
else{
ans += "0"; carry = true;
}
}
if(carry) ans += "1";
reverse(ans.begin(), ans.end());
return ans;
}
};