[LeetCode Road] Add Binary - Solution/C++

67. Add Binary

Question:

Given two binary strings a and b, return their sum as a binary string.

Example:

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

Input: a = "1010", b = "1011"
Output: "10101"

Constraints:

1 <= a.length, b.length <= 10^4

a and b consist only of '0' or '1' characters.

Each string does not contain leading zeros except for the zero itself.

Source code

Version 1

Idea:
I want to post my method originally, but the method is very inefficient (add two elements of string as Plus One, do the same thing for each bits.)

So, I refered to Huahua's Tech Road. Wow, it's a concise approach and coding, use only 1 while() to process.

This part, we can learn how to convert char to integer、how to convert integer to char、calculate a value of carry and output in reverse.

At 9 line, use conditional ? Ture:False to implement one line of if-else statement.
At 12 line, it is a right shift operator.

int a[i] = 1; // binary: 00000001
int b[j] = 1; // binary: 00000001
int sum = a[i] + b[j] = 2 // binary: 00000010
int carry = sum >> 1; // binary: 00000001 (right shifts the bits of the number accordingly)

Then, ues - '0' to convert char to int as a[i--] - '0', because character '0' means 48.

At 13 line, we use logical AND & to get the result of 0 or 1.
Because there are three different value of sum, we need to convert integer to bit, it's shown as the following:

if sum = 0 // binary: 00000000
 (sum & 1) = 0
if sum = 2 // binary: 00000010
 (sum & 1) = 1
if sum = 3 // binary: 00000011
 (sum & 1) = 1

Then, we can use + '0' to convert int to char.
Finally, the variable of res is our answer, but the content is in reverse, so we need to output the last as head, rbegin() and rend() are built-in functions in C++ STL. rbegin() can return a reverse iterator pointing to the last char. rend() can return a reverse iterator pointing to the theoretical element preceding the first char of the string.

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public:
    string addBinary(string a, string b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        string res;
        while(i >= 0 || j >= 0){
            int sum = (i >= 0 ? a[i--] - '0' : 0) +
                      (j >= 0 ? b[j--] - '0' : 0) +
                      carry;
            carry = sum >> 1;
            res += '0' + (sum & 1);
        }
        if(carry) res += '1';
        return {(res.rbegin()), (res.rend())};
    }
};