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:
 “Plus One” (#66) on LeetCode
 “Multiply Strings” (#43) on LeetCode
Reasoning:
These involve operations on numerical digits represented as strings, which is a commonality with the problem “Add Binary”.
“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 carryover 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.
“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.


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:
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.
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 variablecarry
to store the carryover 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 carryover to the next step. The digit in the result is
sum mod 2
and the carryover to the next step issum div 2
.Continue this process until all digits are processed and there is no carryover left.
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 + (ith digit of a)
DECREMENT i
IF j >= 0
carry < carry + (jth 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:
Arithmetic Operations: The problem requires performing an addition operation, which is a fundamental arithmetic operation, albeit with binary numbers instead of decimal numbers.
Binary Number System: This problem specifically deals with the binary number system, which is a base2 system. It requires understanding of binary numbers and their operations.
String Manipulation: Given the binary numbers are provided as strings, it involves handling and manipulating strings.
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 highlevel 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 carryover
WHILE i >= 0 OR j >= 0 OR carry
// If there are digits left in a, add the ith digit of a to carry
IF i >= 0
carry < carry + (ith digit of a)
DECREMENT i
// If there are digits left in b, add the jth digit of b to carry
IF j >= 0
carry < carry + (jth 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.
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).
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.
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.
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.
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.
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.
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.
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.
ProblemSolving Approach:
The problemsolving approach can be described in a stepbystep manner as follows:
Identify the problem: In this case, the problem is to add two binary numbers.
Understand the problem requirements: Binary numbers are provided as strings and need to be added as if they were actual binary numbers.
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.
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.
Test the solution: Test the solution with various inputs to ensure it works as expected in all scenarios.
Targeted Drills in Python
 Variables and Data Types: Understand how to create and use variables of different types.


 Strings and String Manipulation: Learn to manipulate strings  finding length, accessing individual characters, and converting strings to integers.


 Lists and List Manipulation: Learn to manipulate lists  creating a list, adding elements, and converting a list to a string.


 Loops (While Loop): Learn to use while loops for iterative processes.


 Conditions (If Statements): Learn to use if statements for conditional processes.


 Arithmetic Operations: Learn to use arithmetic operations for binary operations.


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:


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 clocklike behavior).
 Functions and/or Methods: Learn to create functions/methods, their inputs and outputs.


 Classes (Optional): Learn to create classes and methods within a class.


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


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.