Problem Statement
Given two binary strings a and b, return their sum as a binary string.
Approach
This is a straight forward problem. We will use the same approach that we use for adding two decimal numbers.
Below are the steps -
- Keep a variable
carry. - Scan the strings from right to left.
- Calculate
sumby adding the two bits represented by the characters and add carry to it. - Take the
summodulo 2 (sum % 2) (because it's binary, duh 😃) and add it in the front of the existing result string. - Update the
carryby takingsum / 2for the next iteration. - Check if the value of the
carryis more than zero after the last iteration and if exists, add it to the front of the result.
And that's it! We have just added two binary srings. We should be proud of ourselves 👏.
The code in Java, JavaScript and Python is below -
Java
public class AddBinary {
public String addBinary(String a, String b) {
// Resultant String
StringBuilder result = new StringBuilder();
// Indices for a and b
int i = a.length() - 1;
int j = b.length() - 1;
// Carry
int carry = 0;
while (i >= 0 || j >= 0) {
// Sum of two bits
int sum = carry;
if (i >= 0) {
sum += a.charAt(i--) - '0';
}
if (j >= 0) {
sum += b.charAt(j--) - '0';
}
// Add the bit to the result
result.insert(0, sum % 2);
// Modify carry
carry = sum / 2;
}
// Final check if carry exists
if (carry > 0) {
result.insert(0, 1);
}
return result.toString();
}
}
JavaScript
var addBinary = function (a, b) {
// Resultant string
let result = "";
// Indices for a and b
let i = a.length - 1;
let j = b.length - 1;
// Carry
let carry = 0;
while (i >= 0 || j >= 0) {
// Sum of two bits
let sum = carry;
if (i >= 0) {
sum += a[i--] - '0';
}
if (j >= 0) {
sum += b[j--] - '0';
}
// Add the bit to the result
result = sum % 2 + result;
// Modify carry
carry = parseInt(sum / 2);
}
// Final check if carry exists
if (carry > 0) {
result = 1 + result;
}
return result;
};
Python
class AddBinary:
def addBinary(self, a: str, b: str) -> str:
# Resultant string
result = ""
# Indices for a and b
aCount = len(a) - 1
bCount = len(b) - 1
# Carry
carry = 0
# Loop for all the characters in the strings
while aCount >= 0 or bCount >= 0:
# Sum of two bits
totalSum = carry
if aCount >= 0:
totalSum += int(a[aCount])
aCount -= 1
if bCount >= 0:
totalSum += int(b[bCount])
bCount -= 1
# Add the bit to te result
result = str(totalSum % 2) + result
# Modify carry
carry = totalSum // 2
# Final check if carry exists
if carry > 0:
result = str(1) + result
return result
Conclusion
I hope you enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.
Feel free to connect with me on Twitter and LinkedIn.
Till next time… Happy coding 😄 and Namaste 🙏!
Top comments (0)