67. Add Binary

EasyBit ManipulationMathStringSimulation
Leetcode Link

Problem Description

Given two strings a and b that represent binary numbers (0 or 1), the goal is to find the sum of these two binary strings and return the result also as a binary string. Binary addition is similar to decimal addition, but it carries over a 1 when the sum of two bits is 2 (since 1 + 1 in binary is 10).

In a simpler form, you are required to add two binary numbers without using built-in binary to decimal conversion functions, and then represent the result as a binary number in string format.

Intuition

The intuition for solving this problem aligns with how we generally perform addition by hand in decimal numbers, but instead we apply binary rules. We begin by adding the least significant bits (rightmost bits) of the input binary strings, a and b. We work our way to the most significant bit (left side) considering any carry that arises from the addition of two bits.

Each bit can only be 0 or 1. If the sum of two bits plus any carry from the previous bit is 2 or 3, a carry of 1 is passed to the next left bit. The binary sum (ignoring the carry) for that position will be 0 if the sum is 2 (since 10 in binary represents 2), or 1 if the sum is 3 (since 11 in binary represents 3).

For positions where one of the strings may have run out of bits (because one string can be shorter than the other), we treat the missing bit as 0. We also need to consider the possibility of a carry remaining after we've finished processing both strings.

The process can be summarized as follows:

  1. Initialize an answer array to build the result string.
  2. Use two pointers starting from the end of both strings and a variable to hold the carry value (initially 0).
  3. Iterate while at least one pointer is valid or there is a carry remaining.
  4. Compute the sum for the current position by adding bits a[i] and b[j] along with the carry.
  5. Use the divmod function to obtain the result for the current position and the new carry.
  6. Append the result to the answer array.
  7. Once the iteration is complete, reverse the answer array to represent the binary sum in the proper order.
  8. Join the answer array elements into a string and return it.

The solution uses divmod for a compact and readable way to handle both the carry and the current bit representation at the same time.

Learn more about Math patterns.

Solution Approach

The implementation employs several important concepts for working with binary numbers:

  • Pointer Iteration: We use two pointers i and j that iterate through both strings a and b, respectively, starting from the end (least significant bit) moving towards the start (most significant bit). This ensures that addition occurs like manual hand addition, from right to left.

  • Carry Handling: We initialize a variable carry to 0, which will be used to handle the carry-over that occurs when the sum of bits exceeds 1.

  • Loop Control: The loop continues as long as there is a bit to process (either i or j is greater than or equal to 0) or there is a carry to apply. The or logic ensures we process all bits and handle the final carry.

  • Bit Addition and Carry Update: Inside the loop, the carry is updated by adding the values of the current bits a[i] and b[j]. We use a conditional expression (0 if i < 0 else int(a[i])) and similarly for b[j] to account for cases where one binary string is shorter than the other; in such cases, the nonexistent bit is considered as 0.

  • Result and Carry Calculation: The carry, v = divmod(carry, 2) line cleverly updates both the carry for the next iteration and the result for the current position. The divmod function is a built-in Python function that takes two numbers and returns a tuple containing their quotient and remainder. Since we are working with binary, dividing by 2 covers both scenarios: if carry is 1 or 2, the quotient would be the next carry, and the remainder would be the bit to append for the current position.

  • Building the Result: The bit for the current position is appended to the ans list. After the loop, we reverse the ans list to obtain the actual binary representation, because we've been adding bits in reverse order, starting from the least significant bit.

  • Result Conversion: Finally, we convert the list of bits into a string using the join() method and return it as the final binary sum.

Here's how the algorithm and its components come into play in the code:

1class Solution:
2    def addBinary(self, a: str, b: str) -> str:
3        ans = []  # List to store the binary result bits
4        i, j, carry = len(a) - 1, len(b) - 1, 0  # Initialize pointers and carry
5
6        # Loop while there are bits to process or a carry
7        while i >= 0 or j >= 0 or carry:
8            # Perform bit addition for current position and update carry
9            carry += (0 if i < 0 else int(a[i])) + (0 if j < 0 else int(b[j]))
10            # Use divmod to get the bit value and the new carry
11            carry, v = divmod(carry, 2)
12            # Append the result bit to the ans list
13            ans.append(str(v))
14            # Move to the previous bits
15            i, j = i - 1, j - 1
16      
17        # Reverse the ans list to get the correct bit order and join to form a binary string
18        return "".join(ans[::-1])

This clean and efficient approach leverages the mechanics of binary addition and takes full advantage of Python's powerful features for readability and concise code.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Example Walkthrough

Let's use a simple example with two binary strings a = "101" and b = "110" to illustrate the solution approach step by step:

  1. Initialization
    We initialize i to 2 (index of the last character of a), j to 2 (index of the last character of b), and carry to 0. Our ans array starts empty.

  2. Iteration 1
    We begin from the end of both strings:

    • i (index 2 of a) corresponds to 1.
    • j (index 2 of b) corresponds to 0.

    Adding these with carry = 0, we get 1 + 0 + 0 = 1.
    carry, v = divmod(1, 2) makes carry = 0 and v = 1.
    ans array becomes ['1'].
    Decrement i and j by 1. Now i = 1, j = 1.

  3. Iteration 2

    • i now points to 0 (a[1])
    • j now points to 1 (b[1])

    Adding these with carry = 0, we get 0 + 1 + 0 = 1.
    carry, v = divmod(1, 2) makes carry = 0 and v = 1.
    ans array becomes ['1', '1'].
    Decrement i and j by 1. Now i = 0, j = 0.

  4. Iteration 3

    • i now points to 1 (a[0])
    • j now points to 1 (b[0])

    Adding these with carry = 0, we get 1 + 1 + 0 = 2.
    carry, v = divmod(2, 2) makes carry = 1 and v = 0.
    ans array becomes ['1', '1', '0'].
    Decrement i and j by 1. Now i = -1, j = -1.

  5. Iteration 4
    Both pointers i and j are less than 0, but we still have carry = 1 to process.
    Since there are no more bits to add (a[-1] and b[-1] don't exist), we only add the carry.
    carry, v = divmod(1, 2) makes carry = 0 and v = 1.
    ans array becomes ['1', '1', '0', '1'].
    Since carry is now 0, we will exit the loop after this step.

  6. Finalizing the Result
    ans is currently ['1', '1', '0', '1'], which is the reverse of our desired binary sum.
    We reverse ans to get ['1', '0', '1', '1'].
    Joining ans we get the binary string "1011" which is the sum of a and b.

Thus, calling Solution().addBinary("101", "110") would return "1011".

Solution Implementation

1class Solution:
2    def addBinary(self, a: str, b: str) -> str:
3        # Initialize result list, pointers for a and b, and carry variable.
4        result = []
5        pointer_a, pointer_b, carry = len(a) - 1, len(b) - 1, 0
6      
7        # Loop until both pointers are out of range and there is no carry left.
8        while pointer_a >= 0 or pointer_b >= 0 or carry:
9            # Add carry to the sum of the current digits from a and b.
10            # Use ternary operator to handle index out of range scenarios.
11            carry += (0 if pointer_a < 0 else int(a[pointer_a])) + \
12                     (0 if pointer_b < 0 else int(b[pointer_b]))
13          
14            # Perform division by 2 to get carry and the value to store.
15            carry, value = divmod(carry, 2)
16          
17            # Append the value to the result list.
18            result.append(str(value))
19          
20            # Move the pointers one step to the left.
21            pointer_a, pointer_b = pointer_a - 1, pointer_b - 1
22      
23        # Since the append operation adds the least significant bits first,
24        # the result string should be reversed to represent the correct binary number.
25        return "".join(result[::-1])
26
27# Example usage:
28solution = Solution()
29print(solution.addBinary("1010", "1011"))  # Output: "10101"
30
1public class Solution {
2    public String addBinary(String a, String b) {
3        // StringBuilder to store the result of the binary sum
4        StringBuilder result = new StringBuilder();
5        // Indices to iterate through the strings from the end to the start
6        int indexA = a.length() - 1;
7        int indexB = b.length() - 1;
8        // Carry will be used for the addition if the sum of two bits is greater than 1
9        int carry = 0;
10        // Loop until all characters are processed or there is no carry left
11        while (indexA >= 0 || indexB >= 0 || carry > 0) {
12            // If still within the bounds of string a, add the numeric value of the bit to carry
13            if (indexA >= 0) {
14                carry += a.charAt(indexA) - '0';
15                indexA--; // Decrement index for string a
16            }
17            // If still within the bounds of string b, add the numeric value of the bit to carry
18            if (indexB >= 0) {
19                carry += b.charAt(indexB) - '0';
20                indexB--; // Decrement index for string b
21            }
22            // Append the remainder of dividing carry by 2 (either 0 or 1) to the result
23            result.append(carry % 2);
24            // Carry is updated to the quotient of dividing carry by 2 (either 0 or 1)
25            carry /= 2;
26        }
27        // Since the bits were added from right to left, the result needs to be reversed to match the correct order
28        return result.reverse().toString();
29    }
30}
31
1#include <algorithm> // include algorithm for using the reverse function
2#include <string>    // include string library to use the string class
3
4class Solution {
5public:
6    // Function to add two binary strings and return the sum as a binary string
7    string addBinary(string a, string b) {
8        string result; // Resultant string to store the binary sum
9
10        // Indices to iterate through strings a and b from the end
11        int indexA = a.size() - 1;
12        int indexB = b.size() - 1;
13      
14        // Iterate over the strings from the end while there is a digit or a carry
15        for (int carry = 0; indexA >= 0 || indexB >= 0 || carry; --indexA, --indexB) {
16          
17            // Add carry and the corresponding bits from a and b. If index is negative, add 0
18            carry += (indexA >= 0 ? a[indexA] - '0' : 0) + (indexB >= 0 ? b[indexB] - '0' : 0);
19          
20            // Append the least significant bit of the carry (either 0 or 1) to the result
21            result.push_back((carry % 2) + '0');
22          
23            // Divide carry by 2 to get the carry for the next iteration
24            carry /= 2; 
25        }
26      
27        // Since the bits were added from right to left, reverse the result to get the correct order
28        reverse(result.begin(), result.end());
29      
30        // Return the resulting binary sum string
31        return result;
32    }
33};
34
1function addBinary(a: string, b: string): string {
2    // Initialize indices for the last characters of strings `a` and `b`
3    let indexA = a.length - 1;
4    let indexB = b.length - 1;
5    // Initialize an array to store the result in reverse order
6    let result: number[] = [];
7    let carry = 0; // This will hold the carry-over for binary addition
8
9    // Loop until both strings are traversed or carry is non-zero
10    while (indexA >= 0 || indexB >= 0 || carry > 0) {
11        // If indexA is valid, add corresponding digit from 'a' to carry
12        if (indexA >= 0) {
13            carry += a[indexA].charCodeAt(0) - '0'.charCodeAt(0);
14            indexA--;
15        }
16        // If indexB is valid, add corresponding digit from 'b' to carry
17        if (indexB >= 0) {
18            carry += b[indexB].charCodeAt(0) - '0'.charCodeAt(0);
19            indexB--;
20        }
21      
22        // The binary digit is carry % 2, add to result
23        result.push(carry % 2);
24        // Update carry for next iteration: divide by 2 and floor
25        carry = Math.floor(carry / 2);
26    }
27  
28    // Since we stored the result in reverse, reverse it back to get the actual result
29    return result.reverse().join('');
30}
31

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the while loop, which continues until the end of the longer of the two binary strings a and b is reached. The loop runs once for each digit in the longer string, plus potentially one additional iteration if there is a carry out from the final addition. If n is the length of the longer string, then at each iteration at most a constant amount of work is done (addition, modulo operation, and index decrease), making the time complexity O(n).

Space Complexity

The space complexity of the code is primarily due to the ans list that accumulates the results of the binary addition. In the worst case, this list will have a length that is one element longer than the length of the longer input string (in the case where there is a carry out from the last addition). This gives us a space complexity of O(n), where n is the length of the longer string.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄