algoadvance

Leetcode 67. Add Binary

Problem Statement:

Given two binary strings a and b, return their sum as a binary string.

Example:

Input: a = "11", b = "1"
Output: "100"

Input: a = "1010", b = "1011"
Output: "10101"

Clarifying Questions:

1. Can the binary strings contain leading zeros?
   • Yes, they can.
2. What is the maximum length of the binary strings?
   • Typical constraints can vary, but assume a reasonable length such as up to 10,000 characters.
3. Do we need to handle invalid input?
   • For simplicity, assume inputs are always valid binary strings.

Strategy:

1. Initialize indices from the end of the strings (a and b).
2. Use a carry variable to keep track of the carry from the previous addition.
3. Traverse the strings from the end to the beginning, adding corresponding digits and the carry.
4. Append the result of each addition to a result string (from the least significant bit to the most significant bit).
5. If there’s a remaining carry after the loop, append it to the result.
6. Reverse the result string before returning it as the function output.

Code:

#include <string>
#include <algorithm>

std::string addBinary(std::string a, std::string b) {
    int i = a.length() - 1;
    int j = b.length() - 1;
    int carry = 0;
    std::string result = "";
    
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        
        if (i >= 0) {
            sum += a[i] - '0';
            i--;
        }

        if (j >= 0) {
            sum += b[j] - '0';
            j--;
        }
        
        carry = sum / 2;
        result += std::to_string(sum % 2);
    }
    
    std::reverse(result.begin(), result.end());
    return result;
}

Explanation:

• We initialize indices i and j at the end of strings a and b respectively.
• The carry variable handles any overflow from the sum of two digits.
• While there are still digits to process in either a or b or there is a carry:
  • Calculate sum as the sum of the carry and the current digits of a and b if available.
  • Update the carry using integer division by 2.
  • Append the current bit (sum % 2) to the result string.
• After the loop, the result string is in reversed order, so we reverse it.
• The final string represents the binary sum.

Time Complexity:

• The time complexity of this algorithm is O(max(n, m)), where n and m are the lengths of strings a and b respectively, because we process each bit once.
• The space complexity is also O(max(n, m)) for the result storage.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?