Jobs

Interviews

Discussions

Add Binary

Easy

Asked by:

More companies

58 views

Topics:

StringsBit Manipulation

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

Example 1:

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

Example 2:

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

Constraints:

1 <= a.length, b.length <= 10⁴
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.

Try coding it in LeetCode

Add Binary

Easy

Asked by:

More companies

58 views

Topics:

StringsBit Manipulation

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

Example 1:

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

Example 2:

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

Constraints:

1 <= a.length, b.length <= 10⁴
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings `a` and `b` be empty or null?
What is the maximum length of the input strings `a` and `b`?
Do the input strings `a` and `b` only contain '0' and '1'?
Should I return an empty string if both inputs are empty or null?
Should the returned binary string have leading zeros? If so, are they allowed or should I remove them?

Brute Force Solution

Approach

The brute force approach to adding binary numbers is similar to how we add numbers by hand, but we do it step-by-step for each binary digit. We will start from the rightmost digits and work our way to the left, keeping track of any carry-over values along the way. We perform the addition at each digit position, combining the digits and any carry, and determining the resulting digit and new carry.

Here's how the algorithm would work step-by-step:

Start by looking at the rightmost digits of both binary numbers.
Add these two digits together. Also, include any carry from a previous addition, if there is one.
Based on the sum (which will be 0, 1, 2, or 3), determine the rightmost digit of the result. The rightmost digit of the result will be the 'ones' place of the sum.
Determine if there is a carry. A carry happens when the sum is 2 or 3.
Move to the next digits to the left in both binary numbers.
Repeat the addition process, including any carry from the previous step.
Continue this process until you have added all digits from both binary numbers and there is no carry left.
If one number is shorter than the other, treat the missing digits as zeros.
The digits you have determined form the result of the binary addition, read from right to left. If there is a carry at the very end, include it as a new leading digit in the result.

Code Implementation

def add_binary(first_binary_string,
        second_binary_string):

    result = ''
    carry = 0
    first_index = len(first_binary_string) - 1
    second_index = len(second_binary_string) - 1

    while first_index >= 0 or second_index >= 0 or carry:

        # Get digit value, or 0 if index out of bounds
        first_digit = int(first_binary_string[first_index]) if first_index >= 0 else 0
        second_digit = int(second_binary_string[second_index]) if second_index >= 0 else 0

        # Calculate the sum of digits and carry
        digit_sum = first_digit + second_digit + carry

        # Determine the resulting digit
        result_digit = str(digit_sum % 2)
        result = result_digit + result

        # Determine if there is a carry for next iteration
        carry = digit_sum // 2

        # Move to the next digits
        first_index -= 1
        second_index -= 1

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the binary strings 'a' and 'b' from right to left, performing addition on corresponding digits. The number of iterations is determined by the length of the longer string. Therefore, the time complexity is directly proportional to the length of the longer string, which we can denote as 'n'. Thus, the time complexity simplifies to O(n).

Space Complexity

O(N) – The space complexity is determined by the size of the result string. In the worst-case scenario, the sum of two N-digit binary numbers can have N+1 digits, requiring a result string of length up to N+1. Therefore, we need auxiliary space to store this result string, which grows linearly with the input size N, where N represents the maximum number of digits in the input binary numbers. This gives us a space complexity of O(N).

Optimal Solution

Approach

The best way to add binary numbers is to mimic how we add regular numbers by hand, but working with only 0s and 1s. We'll process the binary strings from right to left, adding corresponding digits and keeping track of any carry-over.

Here's how the algorithm would work step-by-step:

Start at the rightmost digits of both binary numbers.
Add the two digits together, along with any carry-over from the previous addition. Remember that in binary: 0+0=0, 0+1=1, 1+0=1, and 1+1=10 (which is 0 with a carry-over of 1).
Write down the digit that represents the result of the addition (either 0 or 1).
If the sum of the digits is 2 (1+1), then carry-over a 1 to the next addition step.
Move one position to the left in both binary numbers and repeat steps 2-4.
If one binary number is shorter than the other, treat the missing digits as zeros.
After processing all digits, if there's still a carry-over, add it to the beginning of the result.
The final result is the binary sum of the two input strings.

Code Implementation

def add_binary(first_binary_string, second_binary_string):
    result = ''
    carry = 0
    first_pointer = len(first_binary_string) - 1
    second_pointer = len(second_binary_string) - 1

    while first_pointer >= 0 or second_pointer >= 0:
        # Treat missing digits as zeros.
        first_digit = int(first_binary_string[first_pointer]) if first_pointer >= 0 else 0
        second_digit = int(second_binary_string[second_pointer]) if second_pointer >= 0 else 0

        sum_of_digits = first_digit + second_digit + carry

        # Binary addition rules require modulo 2.
        result = str(sum_of_digits % 2) + result

        # Update the carry for the next iteration.
        carry = sum_of_digits // 2

        if first_pointer >= 0:
            first_pointer -= 1
        if second_pointer >= 0:
            second_pointer -= 1

    # If there's a carry-over after processing all digits, add it to the beginning
    if carry:
        result = '1' + result

    return result

Big(O) Analysis

Time Complexity

O(n) – The runtime complexity is determined by the length of the longer binary string. We iterate through both binary strings from right to left, performing addition on corresponding digits. The number of iterations is bounded by the length of the longer string, which we can denote as n. Each addition step involves a constant number of operations (adding digits and handling the carry). Therefore, the algorithm's runtime grows linearly with the size of the input, resulting in a time complexity of O(n).

Space Complexity

O(N) – The primary auxiliary space usage comes from the result string that stores the binary sum. In the worst-case scenario, the result string can have a length of at most max(len(a), len(b)) + 1, where a and b are the input strings, to accommodate a potential carry. Therefore, the length of the result string is proportional to the length of the longer input string, which we can denote as N. Thus, the space complexity is O(N), where N is the maximum length of the two input binary strings.

Edge Cases

Case	How to Handle
Both input strings are null or empty	Return an empty string as the sum of two empty binary strings is an empty string.
One string is null or empty, the other is not	Return the non-empty string as the sum of an empty binary string and a non-empty one is the non-empty one itself.
Input strings of significantly different lengths	Pad the shorter string with leading zeros or iterate backwards using appropriate index bounds for each string.
Very long input strings that could cause integer overflow when converting to integers	Perform addition bit by bit, simulating manual binary addition, avoiding integer conversion.
Input strings contain characters other than '0' and '1'	Throw an IllegalArgumentException or return an error code indicating invalid input.
Carry-over bit remains after processing all digits	Append the carry-over bit ('1') to the beginning of the result string.
Input strings are very long close to the maximum allowed string size	Ensure the solution does not create excessively large intermediate strings that may lead to memory exhaustion.
Leading zeros in the resulting sum (other than a single '0')	Remove any leading zeros from the result after addition, unless the sum is zero, in which case return "0".

Both input strings are null or empty

How to Handle:

Return an empty string as the sum of two empty binary strings is an empty string.

One string is null or empty, the other is not

How to Handle:

Return the non-empty string as the sum of an empty binary string and a non-empty one is the non-empty one itself.

Input strings of significantly different lengths

How to Handle:

Pad the shorter string with leading zeros or iterate backwards using appropriate index bounds for each string.

Very long input strings that could cause integer overflow when converting to integers

How to Handle:

Perform addition bit by bit, simulating manual binary addition, avoiding integer conversion.

Input strings contain characters other than '0' and '1'

How to Handle:

Throw an IllegalArgumentException or return an error code indicating invalid input.

Carry-over bit remains after processing all digits

How to Handle:

Append the carry-over bit ('1') to the beginning of the result string.

Input strings are very long close to the maximum allowed string size

How to Handle:

Ensure the solution does not create excessively large intermediate strings that may lead to memory exhaustion.

Leading zeros in the resulting sum (other than a single '0')

How to Handle:

Remove any leading zeros from the result after addition, unless the sum is zero, in which case return "0".

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings `a` and `b` be empty or null?
What is the maximum length of the input strings `a` and `b`?
Do the input strings `a` and `b` only contain '0' and '1'?
Should I return an empty string if both inputs are empty or null?
Should the returned binary string have leading zeros? If so, are they allowed or should I remove them?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the rightmost digits of both binary numbers.
Add these two digits together. Also, include any carry from a previous addition, if there is one.
Based on the sum (which will be 0, 1, 2, or 3), determine the rightmost digit of the result. The rightmost digit of the result will be the 'ones' place of the sum.
Determine if there is a carry. A carry happens when the sum is 2 or 3.
Move to the next digits to the left in both binary numbers.
Repeat the addition process, including any carry from the previous step.
Continue this process until you have added all digits from both binary numbers and there is no carry left.
If one number is shorter than the other, treat the missing digits as zeros.
The digits you have determined form the result of the binary addition, read from right to left. If there is a carry at the very end, include it as a new leading digit in the result.

Code Implementation

def add_binary(first_binary_string,
        second_binary_string):

    result = ''
    carry = 0
    first_index = len(first_binary_string) - 1
    second_index = len(second_binary_string) - 1

    while first_index >= 0 or second_index >= 0 or carry:

        # Get digit value, or 0 if index out of bounds
        first_digit = int(first_binary_string[first_index]) if first_index >= 0 else 0
        second_digit = int(second_binary_string[second_index]) if second_index >= 0 else 0

        # Calculate the sum of digits and carry
        digit_sum = first_digit + second_digit + carry

        # Determine the resulting digit
        result_digit = str(digit_sum % 2)
        result = result_digit + result

        # Determine if there is a carry for next iteration
        carry = digit_sum // 2

        # Move to the next digits
        first_index -= 1
        second_index -= 1

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the rightmost digits of both binary numbers.
Add the two digits together, along with any carry-over from the previous addition. Remember that in binary: 0+0=0, 0+1=1, 1+0=1, and 1+1=10 (which is 0 with a carry-over of 1).
Write down the digit that represents the result of the addition (either 0 or 1).
If the sum of the digits is 2 (1+1), then carry-over a 1 to the next addition step.
Move one position to the left in both binary numbers and repeat steps 2-4.
If one binary number is shorter than the other, treat the missing digits as zeros.
After processing all digits, if there's still a carry-over, add it to the beginning of the result.
The final result is the binary sum of the two input strings.

Code Implementation

def add_binary(first_binary_string, second_binary_string):
    result = ''
    carry = 0
    first_pointer = len(first_binary_string) - 1
    second_pointer = len(second_binary_string) - 1

    while first_pointer >= 0 or second_pointer >= 0:
        # Treat missing digits as zeros.
        first_digit = int(first_binary_string[first_pointer]) if first_pointer >= 0 else 0
        second_digit = int(second_binary_string[second_pointer]) if second_pointer >= 0 else 0

        sum_of_digits = first_digit + second_digit + carry

        # Binary addition rules require modulo 2.
        result = str(sum_of_digits % 2) + result

        # Update the carry for the next iteration.
        carry = sum_of_digits // 2

        if first_pointer >= 0:
            first_pointer -= 1
        if second_pointer >= 0:
            second_pointer -= 1

    # If there's a carry-over after processing all digits, add it to the beginning
    if carry:
        result = '1' + result

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both input strings are null or empty	Return an empty string as the sum of two empty binary strings is an empty string.
One string is null or empty, the other is not	Return the non-empty string as the sum of an empty binary string and a non-empty one is the non-empty one itself.
Input strings of significantly different lengths	Pad the shorter string with leading zeros or iterate backwards using appropriate index bounds for each string.
Very long input strings that could cause integer overflow when converting to integers	Perform addition bit by bit, simulating manual binary addition, avoiding integer conversion.
Input strings contain characters other than '0' and '1'	Throw an IllegalArgumentException or return an error code indicating invalid input.
Carry-over bit remains after processing all digits	Append the carry-over bit ('1') to the beginning of the result string.
Input strings are very long close to the maximum allowed string size	Ensure the solution does not create excessively large intermediate strings that may lead to memory exhaustion.
Leading zeros in the resulting sum (other than a single '0')	Remove any leading zeros from the result after addition, unless the sum is zero, in which case return "0".

Both input strings are null or empty

How to Handle:

Return an empty string as the sum of two empty binary strings is an empty string.

One string is null or empty, the other is not

How to Handle:

Return the non-empty string as the sum of an empty binary string and a non-empty one is the non-empty one itself.

Input strings of significantly different lengths

How to Handle:

Pad the shorter string with leading zeros or iterate backwards using appropriate index bounds for each string.

Very long input strings that could cause integer overflow when converting to integers

How to Handle:

Perform addition bit by bit, simulating manual binary addition, avoiding integer conversion.

Input strings contain characters other than '0' and '1'

How to Handle:

Throw an IllegalArgumentException or return an error code indicating invalid input.

Carry-over bit remains after processing all digits

How to Handle:

Append the carry-over bit ('1') to the beginning of the result string.

Input strings are very long close to the maximum allowed string size

How to Handle:

Ensure the solution does not create excessively large intermediate strings that may lead to memory exhaustion.

Leading zeros in the resulting sum (other than a single '0')

How to Handle:

Remove any leading zeros from the result after addition, unless the sum is zero, in which case return "0".