Solving a Leetcode problem daily — Day 4 | Add Binary
Tags: binary, leetcode, string, maths
Published: 2024-05-06 02:32:24

{% embed https://medium.com/@subhradeep_saha/solving-a-leetcode-problem-daily-day-4-add-binary-24a98c1df7c5 %}

---

> Here is the leetcode problem link — [https://leetcode.com/explore/learn/card/array-and-string/203/introduction-to-string/1160/](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

```cpp
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 =&gt; add those =&gt; 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 of**`a`**:**

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](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!