Short code by c++


  • 225
    class Solution
    {
    public:
        string addBinary(string a, string b)
        {
            string s = "";
            
            int c = 0, i = a.size() - 1, j = b.size() - 1;
            while(i >= 0 || j >= 0 || c == 1)
            {
                c += i >= 0 ? a[i --] - '0' : 0;
                c += j >= 0 ? b[j --] - '0' : 0;
                s = char(c % 2 + '0') + s;
                c /= 2;
            }
            
            return s;
        }
    };

  • 0
    H

    beautiful solution.very brief.get it!


  • 8
    E

    ||c==1) this is very smart


  • 0
    B
    c /= 2;
    

    My favorite part. The += on the ternary is quite nice also


  • 0
    S

    beautiful code.


  • 0

    Really nice code! Handle all those cases in a unified manner.


  • 0

    masterpiece!


  • -15
    A

    My solution ,another easy to understand style

    string addBinary(string a, string b)
    {
        int length1 = a.size(), length2 = b.size();
        if(0 == length1) return b;
        if(0 == length2) return a;
        int iIndex1 = length1 - 1, iIndex2 = length2 - 1;
        int ic = 0, ia, ib, sum;
        string output;
        while(iIndex1 != -1 || iIndex2 != -1)
        {
            if(-1 == iIndex1)
                ia = 0;
            else
                ia = a[iIndex1] - '0';
    
            if(-1 == iIndex2)
                ib = 0;
            else
                ib = b[iIndex2] - '0';
    
            sum = ia + ib + ic;
            if(sum >= 2) ic = 1;
    		else ic = 0;
            output.insert(0, sum % 2 == 1 ? "1" : "0");
    
            if(iIndex1 >= 0)
                iIndex1--;
            if(iIndex2 >= 0)
                iIndex2--;
        }
        if(ic)
            output.insert(0, "1");
        return output;
    }

  • 0
    L

    concise than mine! nice!


  • 6
    G

    Doesn't s = char(c % 2 + '0') + s; re-allocate a whole new string everytime?


  • 0
    H
    string addBinary(string a, string b) {
    int carry = 0;
    int len = a.size() > b.size() ? a.size() : b.size();
    string res;
    for (int i = 0; i < len; i++) {
        int na = i < a.size() ? (a[a.size() - 1 - i] - '0') : 0;
        int nb = i < b.size() ? (b[b.size() - 1 - i] - '0') : 0;
        int sum = na + nb + carry;
        res = to_string(sum % 2) + res;
        carry = sum / 2;
    }
    if (carry) res = '1' + res;
    return res;
    

    }


  • 13
    Z

    What's the complexity of this solution, it seems to cost n^2 time, for every loop it will replicate the total string rather than append to it directly.
    Thus, why not reverse it first and reverse the result at last, it will cost O(n) time actually. If I made a mistake, please pointed out to me.


  • 0
    E

    very concise!


  • 1
    C

    The code is very beautiful, but there will be"00" + "0" = "00" and accepted !


  • 0
    G
    string addBinary(string a, string b) {
        if (a.size() < b.size()) { a = string(b.size() - a.size(), '0') + a; }
        else                     { b = string(a.size() - b.size(), '0') + b; }
        
        bool c = 0, tmp = 0;
        for (int i = (int)a.size() - 1; i >= 0; --i) {
            tmp = ((a[i] & 1) + (b[i] & 1) + c) > 1;
            b[i] ^= ((a[i] ^ c) & 1);
            c = tmp;
        }
        
        return c ? "1" + b : b;
    }
    

    '0' = 48 = 0110000

    '1' = 49 = 0110001


  • 0
    X

    @HUSTLX1 why not

    int len = max(a.size(), b.size());
    

  • 0
    W

    You didn't think if there is a leading "0" exist, though the test case seem not include this situation, when I run "00001" "000", the server return "1", but your answer return "00001".


  • 1
    F

    The complexity is O(n^2),

    with following test case, it took 149ms, while O(n) alg only need 6ms.

    "1"
    "1111....1111"   #  total 70000 "1"s
    

    with following test case, it gave back "memory limit exceed" error, while O(n) alg still work fine.

    "1"
    "1111....1111"   #  total 100000 "1"s
    

    It's better to avoid pattern string = char + string in loop. Use s[i] to alter string.

    btw, it seems nobody care about the binary strings starting with multiple zeros,

    Your input
          "0001"
          "0000001"
     Your answer "0000010"
     Expected answer "10"

  • 0
    J

    the one must be master otherwise he can't such piece of code


  • 1
    B

    My accepted answer using bitwise operators

    public String addBinary(String a, String b) {
        int i = a.length() - 1; 
        int j = b.length() - 1;
        int c = 0;
        
        String str = "";
        while (i >= 0 || j >= 0 || c == 1) {
            c += i >= 0 ? a.charAt(i--) - '0': 0;
            c += j >= 0 ? b.charAt(j--) - '0': 0;
            str = (c & 1) + str;
            c = c >> 1;
        }
        
        return str;
    }
    

Log in to reply
 

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