Given two binary strings s1 and s2 consisting of only 0s and 1s. Find the resultant string after adding the two Binary Strings.
Note: The input strings may contain leading zeros but the output string should not have any leading zeros.
Input: s1 = "1101", s2 = "111" Output: 10100 Explanation: 1101 + 111 10100
Input: s1 = "00100", s2 = "010" Output: 110 Explanation: 100 + 10 110
Constraints:
1 ≤s1.size(), s2.size()≤ 106
Approach 01:
-
C++
-
Python
#include <string> #include <unordered_map> #include <algorithm> using namespace std; class Solution { public: string addBinary(string& binary_str1, string& binary_str2) { // Equalize lengths by adding leading zeros int max_len = max(binary_str1.size(), binary_str2.size()); binary_str1 = string(max_len - binary_str1.size(), '0') + binary_str1; binary_str2 = string(max_len - binary_str2.size(), '0') + binary_str2; // Binary addition mapping unordered_map<string, string> binary_mapping = { {"000", "00"}, {"001", "01"}, {"010", "01"}, {"011", "10"}, {"100", "01"}, {"101", "10"}, {"110", "10"}, {"111", "11"} }; string result = ""; char carry = '0'; // Perform binary addition from the least significant digit for (int i = max_len - 1; i >= 0; --i) { string current_sum = string(1, carry) + binary_str1[i] + binary_str2[i]; result = binary_mapping[current_sum][1] + result; carry = binary_mapping[current_sum][0]; } // Handle any remaining carry if (carry == '1') { result = '1' + result; } // Remove leading zeros result.erase(0, result.find_first_not_of('0')); return result.empty() ? "0" : result; } };
class Solution: def addBinary(self, binary_str1: str, binary_str2: str) -> str: # Equalize lengths by adding leading zeros max_len = max(len(binary_str1), len(binary_str2)) binary_str1 = binary_str1.zfill(max_len) binary_str2 = binary_str2.zfill(max_len) # Binary addition mapping binary_mapping = { '000': '00', '001': '01', '010': '01', '011': '10', '100': '01', '101': '10', '110': '10', '111': '11' } result = '' carry = '0' # Perform binary addition from the least significant digit for i in range(1, max_len + 1): digit1 = binary_str1[-i] digit2 = binary_str2[-i] current_sum = carry + digit1 + digit2 result = binary_mapping[current_sum][1] + result carry = binary_mapping[current_sum][0] # Handle any remaining carry if carry == '1': result = '1' + result # Remove leading zeros result = result.lstrip('0') return result if result else '0'
Time Complexity
- Equalizing lengths:
To equalize the lengths of the two binary strings, leading zeros are added. This involves constructing two new strings of size \(O(\max(n, m))\), where \(n\) and \(m\) are the lengths of the input strings. The operation takes \(O(\max(n, m))\).
- Binary addition:
The binary addition loop iterates over the length of the strings, which is \(O(\max(n, m))\). For each character, a constant amount of work is done for the lookup in the binary mapping and string concatenation.
- Removing leading zeros:
Removing leading zeros involves traversing the result string once, which takes \(O(\max(n, m))\).
- Overall Time Complexity:
The overall time complexity is \(O(\max(n, m))\), where \(n\) and \(m\) are the lengths of the two input binary strings.
Space Complexity
- Auxiliary Space:
The main space usage comes from the result string, which requires \(O(\max(n, m))\) space to store the final binary sum. The additional space for the mapping is constant \(O(1)\) because it does not grow with the input size.
- Modified Input Strings:
The input strings
binary_str1
andbinary_str2
are padded to equal length, consuming \(O(\max(n, m))\) space. - Overall Space Complexity:
The overall space complexity is \(O(\max(n, m))\), dominated by the result string and the padded input strings.