Solving a Leetcode problem daily — Day 4 | Add Binary

Here is the leetcode problem link — https://leetcode.com/explore/learn/card/array-and-string/203/introduction-to-string/1160/

1. Problem Statement, Constraints, and Test Case

Problem: Write a function that takes two binary strings (a and b) as input and returns their sum, also represented as a binary string.

Constraints:

• The length of each string (a and b) can range from 1 to 10^4 (10,000) characters.

• Both strings consist only of ‘0’ or ‘1’ characters.

• There are no leading zeros (except for the single digit “0” itself).

Test Case:

• Input: a = "11", b = "1"

• Expected Output: “100” (Equivalent to 4 in decimal)

2. Code

class Solution {
public:
  int binToInt(char a) {
    return a == '1';
  }

  void calculateSumCarryRes(int& carry, int arrSum, string& res) {
    int sum = arrSum + carry;
    carry = sum / 2;
    res = to_string(sum % 2) + res;
  }

  string addBinary(string a, string b) {
    string res = "";
    int i = a.length() - 1, j = b.length() - 1;
    int carry = 0;

    while (i >= 0 && j >= 0) {
      calculateSumCarryRes(carry, binToInt(a[i]) + binToInt(b[j]), res);
      i--;
      j--;
    }

    while (i >= 0) {
      calculateSumCarryRes(carry, binToInt(a[i]), res);
      i--;
    }

    while (j >= 0) {
      calculateSumCarryRes(carry, binToInt(b[j]), res);
      j--;
    }

    if (carry) {
      res = to_string(carry) + res;
    }

    return res == "" ? "0" : res;
  }
};

3. Logic Behind Solving the Problem

Overflow errors will come in case we try to convert the binary strings to decimal numbers => add those => convert the sum to a binary string and return it

We solve this problem by simulating the manual addition process used for decimal numbers. However, since we’re dealing with binary (only 0s and 1s), the process is slightly different. Here’s the core logic:

• Convert characters to numbers: We need to convert the binary characters (‘0’ or ‘1’) to their corresponding numerical values (0 or 1).

• Add corresponding digits: Add the current digits from both strings and handle carry-over.

• Carry-over logic: If the sum of two digits is greater than or equal to 2, there’s a carry-over of 1 to the next digit. In binary, any value greater than 1 results in a carry-over.

• Build the result string: Append the remainder of the sum (either 0 or 1) to the beginning of the result string. Since we’re adding digits in reverse order (starting from the least significant bit), this builds the result correctly.

4. Detailed Explanation of the Code (Line by Line)

a. Helper Functions:

• binToInt(char a): This function takes a character (a) as input and returns 1 if it's '1', otherwise it returns 0. It simply converts the binary character to its numerical value.

• calculateSumCarryRes(int& carry, int arrSum, string& res): This function calculates the sum, carry, and result digit for a single addition step.

i) It takes three arguments by reference: carry (integer to store carry-over), arrSum (the sum of current digit values), and res (string to store the result).

ii) It calculates the total sum by adding carry and arrSum.

iii) It updates the carry value by dividing the sum by 2 (since we're in binary).

iv) It appends the remainder of the sum divided by 2 (which will be 0 or 1) to the beginning of the res string using to_string and the + operator.

b. Main Function:

addBinary(string a, string b): This is the main function that handles the entire binary addition process.

Initialization:

• Initializes an empty string res to store the final result.

• Creates variables i and j as pointers to iterate through the last characters (indices) of strings a and b, respectively.

• Initializes carry to 0 to handle potential carry-over from the addition process.

Main While loop:

• Uses a while loop that iterates as long as both i and j are within the valid range of their respective strings (i.e., not negative):

• Calls the calculateSumCarryRes function to calculate the sum, carry, and append the result digit to res. This essentially adds the corresponding digits from both strings and handles carry-over.

• Decrements i and j to move on to the next characters in the strings.

Additional while loops for input strings of different sizes:

• The first loop iterates through the remaining characters of a (if i is still positive) using the same logic as the main loop (calling calculateSumCarryRes). This adds any remaining digits from the longer string a.

• The second loop iterates through the remaining characters of b (if j is still positive) using the same logic (calling calculateSumCarryRes). This adds any remaining digits from the longer string b.

Handling carry over:

• If there’s a carry-over left after processing all the digits (carry is not 0), it's appended to the beginning of res using to_string and the + operator.

Edge case handling:

• At the end lies a ternary operator that checks if res is empty (meaning both input strings were "0"). If so, it returns "0" to ensure a valid output (empty string is not be the expected output behaviour).

5. Walkthrough of the Code for a Test Case

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

Step-by-Step Breakdown:

1. Initialization:res is empty, i = 1 (pointing to the last character of "11"), j = 0 (pointing to the last character of "1"), carry = 0.

2. Main Loop:

Iteration 1:

• Add binToInt(a[i]) (1) and binToInt(b[j]) (1), resulting in a sum of 2.

• Since the sum is greater than or equal to 2, there’s a carry-over of 1 (carry is updated to 1).

• The remainder of the sum divided by 2 (which is 0) is appended to res (initially empty, becomes "0").

• Decrement i and j.

Remaining Digits ofa:

Add binToInt(a[i]) (1) and carry (1), resulting in a sum of 2.

• Similar to the previous iteration, carry-over is 1 and the remainder (0) is appended to res (becomes "00").

• Decrement i. Since j is already -1 (out of bounds), the second while loop for remaining digits of b is skipped.

Carry-Over Handling:

• Since carry is still 1 after processing all digits, it's appended to the beginning of res resulting in the final output: res = "100".

Output: “100” (Equivalent to 4 in decimal)

6. Real-Life Applications of this Problem

While adding binary strings might seem like a theoretical exercise, it has several practical applications in the world of computers:

1. Computer Arithmetic: Binary addition forms the core of arithmetic operations in computers. CPUs use binary addition circuits to perform calculations like addition, subtraction, multiplication, and division on binary numbers representing data.

2. Error Detection and Correction: Communication protocols often employ techniques like checksums or parity bits to detect errors during data transmission. These techniques rely on binary addition to create a redundant value that can be compared to the received data to identify inconsistencies.

3. Computer Graphics: Binary addition plays a role in various aspects of computer graphics, such as color representation and image manipulation. Algorithms for blending colors or manipulating pixel values often involve binary addition operations.

By understanding binary addition, we gain a deeper insight into how computers perform calculations, handle data, and implement various functionalities. It’s a foundational concept in computer science and essential for anyone interested in how computers work at the core level.

7. Conclusion

This blog post has explored the challenge of adding binary strings in C++. I have broken down the problem statement, code, logic, and real-world applications. Feel free to experiment with different test cases and challenge yourself further!

If you liked this post, do applaude this story by clicking on the clap hands button and follow me https://medium.com/@subhradeep_saha. You can checkout my other Leetcode problem explanation posts in my profile page.

Do let me know in the comments in case of any feedback you have for the article. Thanks!

8.References

Cover Photo by Alexander Sinn on Unsplash