Description:
Given two binary strings a and b, return their sum as a binary string.
Examples:
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"Solution in Python:
Python
class Solution:
def addBinary(self, a: str, b: str) -> str:
# Initialize result string and carry
result = ""
carry = 0
# Pad the shorter string with leading zeros to make them of equal length
max_len = max(len(a), len(b))
a = a.zfill(max_len)
b = b.zfill(max_len)
# Traverse both strings from the last character to the first
for i in range(max_len - 1, -1, -1):
# Convert binary characters to integers and add them along with carry
bit_sum = int(a[i]) + int(b[i]) + carry
# Calculate the bit to be added to the result
result_bit = bit_sum % 2
result = str(result_bit) + result
# Update the carry for the next iteration
carry = bit_sum // 2
# If there is a carry left at the end, add it to the result
if carry:
result = "1" + result
return result
# Example usage
solution = Solution()
print(solution.addBinary("11", "1")) # Output: "100"
print(solution.addBinary("1010", "1011")) # Output: "10101"Explanation:
- Initialization:
resultis an empty string that will hold the final binary result.carryis initialized to 0 to handle the sum overflow.
- Padding:
max_lenis the maximum length of the two input strings.a.zfill(max_len)andb.zfill(max_len)ensure both strings have the same length by padding the shorter string with leading zeros.
- Summation Loop:
- The loop iterates from the end (least significant bit) to the beginning (most significant bit) of the binary strings.
bit_sumcalculates the sum of corresponding bits froma,b, and the carry.result_bitis the bit to be appended to the result string, calculated using modulo operation (bit_sum % 2).carryis updated to the integer division ofbit_sumby 2 (bit_sum // 2).
- Final Carry:
- If there is a leftover carry after processing all bits, it is prepended to the result.
- Example Usage:
- The example usage demonstrates how to create an instance of the
Solutionclass and call theaddBinarymethod with different inputs.
- The example usage demonstrates how to create an instance of the
This approach ensures the binary addition is performed correctly and efficiently by iterating through the strings only once.
Solution in Javascript:
JavaScript
/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function(a, b) {
// Initialize result string and carry
let result = "";
let carry = 0;
// Pad the shorter string with leading zeros to make them of equal length
let maxLen = Math.max(a.length, b.length);
a = a.padStart(maxLen, '0');
b = b.padStart(maxLen, '0');
// Traverse both strings from the last character to the first
for (let i = maxLen - 1; i >= 0; i--) {
// Convert binary characters to integers and add them along with carry
let bitSum = parseInt(a[i]) + parseInt(b[i]) + carry;
// Calculate the bit to be added to the result
let resultBit = bitSum % 2;
result = resultBit + result;
// Update the carry for the next iteration
carry = Math.floor(bitSum / 2);
}
// If there is a carry left at the end, add it to the result
if (carry) {
result = '1' + result;
}
return result;
};
// Example usage
console.log(addBinary("11", "1")); // Output: "100"
console.log(addBinary("1010", "1011")); // Output: "10101"Solution in Java:
Java
class Solution {
public String addBinary(String a, String b) {
// Initialize a StringBuilder for the result and carry
StringBuilder result = new StringBuilder();
int carry = 0;
// Pad the shorter string with leading zeros to make them of equal length
int maxLen = Math.max(a.length(), b.length());
a = String.format("%" + maxLen + "s", a).replace(' ', '0');
b = String.format("%" + maxLen + "s", b).replace(' ', '0');
// Traverse both strings from the last character to the first
for (int i = maxLen - 1; i >= 0; i--) {
// Convert binary characters to integers and add them along with carry
int bitSum = (a.charAt(i) - '0') + (b.charAt(i) - '0') + carry;
// Calculate the bit to be added to the result
int resultBit = bitSum % 2;
result.append(resultBit);
// Update the carry for the next iteration
carry = bitSum / 2;
}
// If there is a carry left at the end, add it to the result
if (carry != 0) {
result.append(carry);
}
// The result is built in reverse order, so reverse it back
return result.reverse().toString();
}
}
// Example usage
public class Main {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.addBinary("11", "1")); // Output: "100"
System.out.println(solution.addBinary("1010", "1011")); // Output: "10101"
}
}Solution in C#:
C#
public class Solution {
public string AddBinary(string a, string b) {
// Initialize a StringBuilder for the result and carry
StringBuilder result = new StringBuilder();
int carry = 0;
// Find the maximum length between the two strings
int maxLen = Math.Max(a.Length, b.Length);
// Pad the shorter string with leading zeros to make them of equal length
a = a.PadLeft(maxLen, '0');
b = b.PadLeft(maxLen, '0');
// Traverse both strings from the last character to the first
for (int i = maxLen - 1; i >= 0; i--) {
// Convert binary characters to integers and add them along with carry
int bitA = a[i] - '0';
int bitB = b[i] - '0';
int bitSum = bitA + bitB + carry;
// Calculate the bit to be added to the result
int resultBit = bitSum % 2;
result.Insert(0, resultBit); // Append the resultBit to the front of the result
// Update the carry for the next iteration
carry = bitSum / 2;
}
// If there is a carry left at the end, add it to the result
if (carry != 0) {
result.Insert(0, carry);
}
return result.ToString();
}
}