67. Add Binary - Leetcode Solution
Solution code💡 Step-by-Step Thought Process
- Understand the problem: Add two binary strings and return their sum as a binary string.
- Convert the binary strings a and b to integers using base-2 conversion.
- While b is not zero, perform binary addition without converting to decimal:
- Compute the sum without carry using XOR (a ^ b).
- Compute the carry using AND (a & b) and left-shift it by 1.
- Update a to the sum without carry and b to the carry.
- Convert the final integer a to a binary string, removing the "0b" prefix, and return it.
Code Solution
class Solution:
def addBinary(self, a, b) -> str:
a, b = int(a, 2), int(b, 2)
while b:
without_carry = a ^ b
carry = (a & b) << 1
a, b = without_carry, carry
return bin(a)[2:]
# Time: O(A + B)
# Space: O(1)class BigInt {
private:
string binary;
// Helper function to ensure strings are the same length
static void equalizeLength(string& a, string& b) {
int lengthDifference = a.size() - b.size();
if (lengthDifference > 0)
b.insert(0, lengthDifference, '0');
else
a.insert(0, -lengthDifference, '0');
}
// Helper function to remove leading zeros
void removeLeadingZeros() {
// Erase leading zeros while keeping at least one zero if the number is
// zero
auto firstNonZero = binary.find_first_not_of('0');
if (firstNonZero != string::npos) {
binary.erase(0, firstNonZero);
} else {
binary =
"0"; // Adjust to maintain a minimum representation of zero
}
}
public:
BigInt() : binary("0") {}
// Constructor from a binary string
BigInt(const string& bin) : binary(bin) { removeLeadingZeros(); }
// Bitwise XOR
BigInt operator^(const BigInt& other) const {
string a = binary;
string b = other.binary;
equalizeLength(a, b);
string result;
for (size_t i = 0; i < a.size(); i++) {
char xorChar = (a[i] == b[i] ? '0' : '1');
result.push_back(xorChar);
}
return BigInt(result);
}
// Bitwise AND
BigInt operator&(const BigInt& other) const {
string a = binary;
string b = other.binary;
equalizeLength(a, b);
string result;
for (size_t i = 0; i < a.size(); i++) {
char andChar = (a[i] == '1' && b[i] == '1' ? '1' : '0');
result.push_back(andChar);
}
return BigInt(result);
}
// Left shift
BigInt operator<<(int shift) const {
string result = binary;
result.append(shift, '0');
return BigInt(result);
}
// Check if BigInt is zero
bool isZero() const {
for (char c : binary)
if (c != '0') return false;
return true;
}
// Getter for binary string
string getBinary() const { return binary; }
};
class Solution {
public:
string addBinary(string a, string b) {
BigInt x(a);
BigInt y(b);
BigInt carry, answer;
while (!y.isZero()) {
answer = x ^ y;
carry = (x & y) << 1;
x = answer;
y = carry;
}
return x.getBinary();
}
};import java.math.BigInteger;
public class Solution {
public String addBinary(String a, String b) {
// Convert the binary strings to BigInteger
BigInteger x = new BigInteger(a, 2);
BigInteger y = new BigInteger(b, 2);
// Perform the binary addition using bitwise operations
while (y.compareTo(BigInteger.ZERO) != 0) {
BigInteger withoutCarry = x.xor(y);
BigInteger carry = x.and(y).shiftLeft(1);
x = withoutCarry;
y = carry;
}
// Convert the result back to binary and return it as a string
return x.toString(2);
}
}
var addBinary = function(a, b) {
// Convert the binary strings to BigInt
let x = BigInt("0b" + a);
let y = BigInt("0b" + b);
// Perform the binary addition using bitwise operations
while (y !== 0n) {
let withoutCarry = x ^ y;
let carry = (x & y) << 1n;
x = withoutCarry;
y = carry;
}
// Convert the result back to binary and return it as a string
return x.toString(2);
};
Detailed Explanation
Understanding the Add Binary Problem
The Add Binary problem requires performing binary addition on two input strings representing binary numbers. This is a classic bit manipulation task that mimics how addition works at the binary level, making it particularly relevant for technical interviews and low-level programming.
The goal is to return the sum of these binary numbers as a string, without converting them to integers in a naïve or language-specific way. This ensures we build a solution that handles large inputs that could overflow integer limits in some environments.
Strategy for Adding Binary Strings
A straightforward and effective way to solve this is to simulate binary addition using a loop. Start by initializing two pointers at the end of each binary string. Loop through both strings from right to left, adding the corresponding bits along with a carry value. Append the result of each bit addition to a list, which is reversed at the end to produce the final binary string.
Alternatively, for a more elegant and performant solution, you can convert the strings to integers using base-2 conversion and use bitwise operations to simulate binary addition:
- XOR (a ^ b): Adds the bits without considering the carry.
- AND (a & b) << 1: Calculates the carry by identifying positions where both bits are 1, and shifts it left for the next position.
- Repeat until there’s no carry left (i.e., b becomes 0).
Finally, convert the result back to a binary string and remove the "0b" prefix that comes from Python’s binary format.
Time and Space Complexity
- Time Complexity: O(max(m, n)), where m and n are the lengths of the input strings. Each bit is processed once.
- Space Complexity: O(max(m, n)), as the output string or list storing the result will grow with the size of the inputs.
Why This Approach Works
This approach mimics the exact process used in hardware and low-level programming for binary addition, making it extremely efficient. The use of XOR and AND for summing and carrying ensures constant-time operations on each bit, which scales linearly with input size. It also avoids the need for string-to-integer conversion in languages that don't support big integers.
Conclusion
Solving the Add Binary problem improves your understanding of bitwise operations, carry propagation, and string manipulation. It’s a foundational problem that paves the way for mastering binary math, bit manipulation algorithms, and efficient number processing in memory-constrained systems.