Question Details:
- LeetCode Number: 67
- Difficulty Level: Easy
- Question:You are given two binary strings, a and b.
- Return their sum as a binary string.
- Input: a = "11", b = "1"
- Output: "100"
Questions to be Asked the Interviewer:
- Can the input strings be empty?
- Are there any constraints on the length of the input strings?
Edge Cases for this Problem:
- One or both of the binary strings are empty.
- Both binary strings are '0'.
Available Approaches to Solve this Problem:
- Convert the binary strings to integers, add them, and convert the result back to a binary string.
- Iterate through the strings from right to left, performing binary addition, and manage the carry.
My Approach to Solve this Problem:
- I will use the second approach, performing binary addition, and managing the carry.
- Algorithm and Data Structure Classification: This problem falls under simple string manipulation and arithmetic calculations.
def addBinary(a: str, b: str) -> str:
? ? result = []
? ? carry = 0
? ? i, j = len(a) - 1, len(b) - 1
? ??
? ? while i >= 0 or j >= 0 or carry:
? ? ? ? sum_val = carry
? ? ? ? if i >= 0:
? ? ? ? ? ? sum_val += int(a[i])
? ? ? ? ? ? i -= 1
? ? ? ? if j >= 0:
? ? ? ? ? ? sum_val += int(b[j])
? ? ? ? ? ? j -= 1
? ? ? ? carry = sum_val // 2
? ? ? ? result.append(str(sum_val % 2))
? ??
? ? return ''.join(result[::-1])
Explanation to a Non-Technical Person:
- Imagine you are adding two numbers written on paper, starting from the rightmost digit, and carrying over if the sum is greater than or equal to 2.
- We do the same with the two binary strings, adding each corresponding pair of digits from right to left.
- If the sum of a pair of digits is 2 or more, we carry over to the next left pair.
- The final answer is built by putting these sums together.
Code in Detail:
- Line 1-2: Defining the function to take two binary strings a and b.
- Line 3: Creating an empty list called result to store the sum of each pair of digits.
- Line 4: Initializing a variable called carry to handle any carry-over from the addition.
- Line 5: Initializing two pointers, i and j, to the end of the strings a and b, respectively.
- Line 7: Starting a loop that continues as long as there are digits left in either string or there is a carry.
- Line 8-15: Adding the corresponding digits of a and b and the carry (if any), and updating the carry.
- Line 16: Appending the remainder of the division by 2 (either 0 or 1) to the result.
- Line 18: Reversing the result list and converting it into a string to get the final answer.
Pattern of this Problem:
This problem follows the pattern of iterating through two strings and performing arithmetic operations. It involves understanding binary arithmetic and handling carry-over in addition.
Big O Notation:
- Time Complexity: O(max(n, m)), where n and m are the lengths of the input strings a and b. The time complexity is determined by the length of the longest input string, as we iterate through both strings from right to left.
- Space Complexity: O(max(n, m)), as the resulting string may be as long as the longest input string plus one (in case of a carry-over in the leftmost addition).
Points to Remember to Solve this Problem in the Future:
- Handle the binary addition manually.
- Be cautious with carry-over, especially when one string is longer than the other.
- Don't forget to reverse the result, as the addition is performed from right to left.
Code Line by Line with Some Sample Data:
- Input: a = "11", b = "1"
- Line 3: result is initialized as an empty list.
- Line 4: carry is initialized as 0.
- Line 7: Enters the loop; since both i and j are greater or equal to 0, and carry is 0.
- Line 8-15: Adds the digits from a and b and the carry, calculates the new carry.
- Line 16: Appends '0' or '1' to result.
- Line 18: Converts result into the final binary string "100".
Key Syntax Used in this Solution:
- String manipulation (e.g., accessing characters by index, joining characters into a string).
- Integer division // to calculate the carry.
- Modulo operation % to determine the remainder.
- List reversal [::-1] to reverse the result list.
