Simple and fast C++ solution using vector


  • 0
    D

    A lot of the simpler C++ solutions suffer from using string concatenation on every iteration, which makes them take order n^2 steps. This simple solution computes the solution in linear time by building the result backwards in a vector, then reversing it. This allows it to avoid having to pre-compute the size of the result, making it simpler. It's also easier and faster to simply add the values and then extract the two bits of the sum, rather than compute each bit separately.

    class Solution {
    public:
        string addBinary(string a, string b) {
            vector<char> result;
            int carry = 0;
            for (int ai = a.length() - 1, bi = b.length() - 1; ai >= 0 || bi >= 0; ai--, bi--) {
                int a_val = ai < 0 ? 0 : (a[ai] - '0');
                int b_val = bi < 0 ? 0 : (b[bi] - '0');
                int sum = a_val + b_val + carry;
                result.push_back((sum & 1) + '0');
                carry = sum >> 1;
            }
            if (carry) result.push_back('1');
            reverse(result.begin(), result.end());
            return string(result.begin(), result.end());
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.