Add Binary

Clarification Questions

What are the clarification questions we can ask about this problem?

Identifying Problem Isomorphism

“Add Binary” can be approximately mapped to the following problems:

  1. “Plus One” (#66) on LeetCode
  2. “Multiply Strings” (#43) on LeetCode

Reasoning:

These involve operations on numerical digits represented as strings, which is a commonality with the problem “Add Binary”.

  1. “Plus One” is slightly simpler compared to “Add Binary”. The task in both problems involves adding numbers. However, in “Plus One”, we are adding one to the last digit of a number represented as an array of digits. The carry-over concept in “Add Binary” is similar to the one in “Plus One”, but “Add Binary” has an extra layer of complexity due to the need to add binary numbers.

  2. “Multiply Strings” is more complex compared to “Add Binary”. Here, the problem is to multiply two numbers represented as strings. It’s an operation on numerical digits similar to “Add Binary” but involves a more complicated operation (multiplication vs addition).

While these problems are not exact isomorphs of “Add Binary”, they involve similar operations to be performed on numerical digits.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
  def addBinary(self, a: str, b: str) -> str:
    s = []
    carry = 0
    i = len(a) - 1
    j = len(b) - 1

    while i >= 0 or j >= 0 or carry:
      if i >= 0:
        carry += int(a[i])
        i -= 1
      if j >= 0:
        carry += int(b[j])
        j -= 1
      s.append(str(carry % 2))
      carry //= 2

    return ''.join(reversed(s))

How to go from: Add two given binary and return the result to the pseudocode?

Here are the steps to go from the problem statement “Add two given binary and return the result” to the pseudocode:

  1. Understand the problem: The problem is asking to add two binary numbers. Each binary number is represented as a string. The output should be the sum of these two binary numbers, also represented as a binary string.

  2. Devise a plan: To solve this problem, you can use a basic approach that is similar to how we do addition manually on paper, starting from the rightmost (least significant) digit and moving to the left, carrying over any ‘overflow’ to the next digit. Here’s how you can do it:

    • First, initialize an empty list s to store the result and a variable carry to store the carry-over from each step of the addition.

    • Start from the rightmost digit of both binary strings and move towards the left. In each step, add the corresponding digits from both binary strings along with the carry from the previous step.

    • The sum can be either 0, 1, 2, or 3. If it’s 2 or 3, there is a carry-over to the next step. The digit in the result is sum mod 2 and the carry-over to the next step is sum div 2.

    • Continue this process until all digits are processed and there is no carry-over left.

  3. Write the pseudocode:

FUNCTION addBinary(a, b)
    s <- EMPTY_LIST
    carry <- 0
    i <- last index of a
    j <- last index of b

    WHILE i >= 0 OR j >= 0 OR carry
        IF i >= 0
            carry <- carry + (i-th digit of a)
            DECREMENT i
        IF j >= 0
            carry <- carry + (j-th digit of b)
            DECREMENT j

        APPEND carry mod 2 TO s
        carry <- carry div 2

    result <- JOIN REVERSED s INTO A STRING
    RETURN result
END FUNCTION

This pseudocode follows the plan above, and it effectively solves the problem as stated.

Problem Classification

This problem can be classified under the following categories:

  1. Arithmetic Operations: The problem requires performing an addition operation, which is a fundamental arithmetic operation, albeit with binary numbers instead of decimal numbers.

  2. Binary Number System: This problem specifically deals with the binary number system, which is a base-2 system. It requires understanding of binary numbers and their operations.

  3. String Manipulation: Given the binary numbers are provided as strings, it involves handling and manipulating strings.

  4. Data Conversion: The problem involves converting data from one type to another. In this case, conversion between binary (in string format) and decimal (integer format) is required to perform the operation.

These categories give a high-level classification of the problem domain and can be useful in determining what kind of knowledge and skills are needed to tackle the problem.

Pseudocode

FUNCTION addBinary(a, b)
    // Initialize an empty list for the sum, and pointers at the end of a and b
    s <- EMPTY_LIST
    carry <- 0
    i <- last index of a
    j <- last index of b

    // Loop as long as there are digits left in a or b or there is a carry-over
    WHILE i >= 0 OR j >= 0 OR carry
        // If there are digits left in a, add the i-th digit of a to carry
        IF i >= 0
            carry <- carry + (i-th digit of a)
            DECREMENT i

        // If there are digits left in b, add the j-th digit of b to carry
        IF j >= 0
            carry <- carry + (j-th digit of b)
            DECREMENT j

        // Append the least significant digit of carry to s
        APPEND carry mod 2 TO s

        // Update carry to the most significant digit of carry
        carry <- carry div 2

    // s now holds the digits of the sum in reverse order, so reverse s and join into a string
    result <- JOIN REVERSED s INTO A STRING
    RETURN result
END FUNCTION

In this pseudocode, mod is the modulus operator that gives the remainder of a division, div is the integer division operator that gives the quotient of a division, APPEND item TO list adds item to the end of list, DECREMENT i subtracts 1 from i, and JOIN items INTO A STRING concatenates items into a single string.

Language Agnostic Coding Drills

The given Python code is for adding two binary numbers represented as strings.

  1. Variables and Data Types: Understanding what variables are and the types of data they can hold is fundamental. In this code, variables are used to hold the inputs (a, b), the carry from each addition, the current indices (i, j) being considered in the inputs, and the result (s).

  2. Strings and String Manipulation: Understanding how to work with strings is important here because the binary numbers are represented as strings. It’s necessary to know how to get the length of a string, access individual characters, and convert strings to integers. It’s also necessary to understand string joining and reversing.

  3. Lists and List Manipulation: Lists are used to store the result before it is converted back to a string. Understanding how to create a list, add elements to it, and convert a list to a string is crucial.

  4. Loops (While Loop): The while loop is used to iterate over the binary strings. The carry from each addition must be considered until there’s nothing left to add. Understanding how a while loop works and how to control its execution is critical here.

  5. Conditions (If Statements): If statements are used to check if there are more bits to consider in the input strings and if there’s a carry from a previous addition. Understanding how if statements work is key here.

  6. Arithmetic Operations: Basic arithmetic operations are used for the binary addition. Addition and modulus operations are used to compute the sum and carry, and integer division is used to update the carry.

  7. Functions and/or Methods: The code is written in a method of a class. Understanding how functions/methods work, including their inputs and outputs, is essential.

  8. Classes (Optional): Although not necessary for this specific problem, understanding classes would be helpful for overall understanding as the method is encapsulated within a class in this code.

Problem-Solving Approach:

The problem-solving approach can be described in a step-by-step manner as follows:

  1. Identify the problem: In this case, the problem is to add two binary numbers.

  2. Understand the problem requirements: Binary numbers are provided as strings and need to be added as if they were actual binary numbers.

  3. Break down the problem: The problem can be broken down into simpler tasks:

    • Start from the least significant bit of each string.
    • Add the bits together, including any carry from the previous addition.
    • Record the result and update the carry.
    • Move to the next bit.
    • Repeat until there are no more bits and no carry.
    • Join the results and reverse the string to get the final output.

  4. Develop a solution: The solution can be written in pseudocode as follows:

    • Initialize variables for the result, carry, and the current indices in the strings.
    • While there’s a bit left in either string or a carry:
      • If there’s a bit left in the first string, add it to the carry and decrement the index.
      • If there’s a bit left in the second string, add it to the carry and decrement the index.
      • Append the carry modulus 2 to the result and update the carry using integer division by 2.
    • Join the result into a string, reverse it, and return it.

  5. Test the solution: Test the solution with various inputs to ensure it works as expected in all scenarios.

Targeted Drills in Python

  1. Variables and Data Types: Understand how to create and use variables of different types.
1
2
3
4
5
6
7

# Integer
number = 10
print(number)

# String
text = "Hello, world!"
print(text)
  1. Strings and String Manipulation: Learn to manipulate strings - finding length, accessing individual characters, and converting strings to integers.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

binary_string = "101"

# Length of string
length = len(binary_string)
print(length)

# Accessing character
first_char = binary_string[0]
print(first_char)

# Converting string to integer
number = int(binary_string, 2)  # Base 2 for binary
print(number)
  1. Lists and List Manipulation: Learn to manipulate lists - creating a list, adding elements, and converting a list to a string.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# Create a list
numbers = []

# Add elements
numbers.append(1)
numbers.append(0)
numbers.append(1)
print(numbers)

# Convert list to string
string_numbers = ''.join(map(str, numbers))
print(string_numbers)
  1. Loops (While Loop): Learn to use while loops for iterative processes.
1
2
3
4

count = 0
while count < 5:
    print(count)
    count += 1
  1. Conditions (If Statements): Learn to use if statements for conditional processes.
1
2
3

number = 10
if number > 5:
    print("Number is greater than 5")
  1. Arithmetic Operations: Learn to use arithmetic operations for binary operations.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# Addition
add = 1 + 1
print(add)

# Modulus operation
mod = 10 % 2
print(mod)

# Integer division
div = 10 // 3
print(div)

The modulus operator in Python is denoted by the percent symbol (%). It is a mathematical operator that returns the remainder of the division of the number before the operator by the number after the operator.

Here is an example:

1

print(10 % 3)  # Outputs: 1

In this example, 10 divided by 3 is 3 remainder 1. Therefore, 10 % 3 returns 1.

The modulus operator is commonly used in programming for tasks such as determining if a number is even or odd (i.e., num % 2 would return 0 for even numbers and 1 for odd numbers), or wrapping values within a certain range (for instance, to create a circular array or clock-like behavior).

  1. Functions and/or Methods: Learn to create functions/methods, their inputs and outputs.
1
2
3
4

def greet(name):
    return "Hello, " + name

print(greet("world"))
  1. Classes (Optional): Learn to create classes and methods within a class.
1
2
3
4
5
6

class Greeter:
    def greet(self, name):
        return "Hello, " + name

greeter = Greeter()
print(greeter.greet("world"))

Problem-Specific Drill:

This problem specifically deals with binary addition which is a bit different from usual decimal addition. Learn how to perform binary addition manually.

1
2
3
4
5
6

binary1 = '101'
binary2 = '111'

# Convert to integer, add them and convert back to binary
result = bin(int(binary1, 2) + int(binary2, 2))[2:]
print(result)

After each of these drills, the learner should be equipped with all the necessary skills to implement the addBinary function. The drills should be combined, adjusting as necessary, into the final solution.