Problem 41 - Add Binary
Explore our archive for previous posts.
Question
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = "11", b = "1"
Output: "100"Example 2:
Input: a = "1010", b = "1011"
Output: "10101"Constraints:
1 <= a.length, b.length <= 10^4aandbconsist only of'0'or'1'characters.Each string does not contain leading zeros except for the zero itself.
Approach
The high-level approach for adding two binary numbers represented as strings is as follows:
Initialize a result string to store the sum.
Start from the rightmost (least significant) digits of both binary strings.
Simulate the addition from right to left while considering any carry from the previous step.
For each digit, add it to the current sum, along with the carry from the previous step.
If the sum is 0 or 1, add it to the result string and set the carry to 0.
If the sum is 2, add 0 to the result and set the carry to 1.
If the sum is 3, add 1 to the result and set the carry to 1.
Continue this process for all digits, moving from right to left.
After processing all digits, if there is still a carry, add it as the most significant digit.
The result string now contains the binary sum of the two input binary strings.
This approach avoids converting binary strings to integers and efficiently calculates the sum, handling any carry that occurs during the addition.
Solution
Solve it here
public class Solution {
public String addBinary(String a, String b) {
// Initialize a StringBuilder to store the result.
StringBuilder result = new StringBuilder();
// Initialize a variable to keep track of the carry.
int carry = 0;
// Start from the rightmost digits of string a and b.
int i = a.length() - 1;
int j = b.length() - 1;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry; // Initialize sum with the current carry.
if (i >= 0) {
sum += a.charAt(i) - '0'; // Add the current digit of string a to the sum.
i--; // Move to the next digit of string a.
}
if (j >= 0) {
sum += b.charAt(j) - '0'; // Add the current digit of string b to the sum.
j--; // Move to the next digit of string b.
}
carry = sum / 2; // Calculate the carry for the next iteration.
result.insert(0, sum % 2); // Insert the current bit in the result.
}
return result.toString();
}
}Time and space complexity
Time Complexity: The time complexity of the solution is O(max(N, M)), where N and M are the lengths of the input strings. This is because the algorithm iterates through both strings from right to left once and the time complexity is linear in the length of the longer input string.
Space Complexity: The space complexity is also O(max(N, M)) because the result string stores the sum of the two binary numbers, which can be of similar length to the longer input string.
Explore more?
Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!
