Simple C++ solution with linear comlexity, 40ms


  • 1
    L

    There are three details:

    1.assert the length of a is longer than b, otherwise, return addBinary(b,a);

    2.convert the char a[i],b[j] to int by using a[i]-'0', b[j]-'0' and so on;

    3.if the final carry equals 1, add char '1' ahead of the final result string;

    class Solution {
    public:
        string addBinary(string a, string b) {
            if(a.size()<b.size()) return addBinary(b,a);
    
            int carry=0,j=b.size()-1;           
            char tmp;
            for(int i=a.size()-1;i>=0;i--)
            {   
                if(j<0) {j=0;b[j]='0';}
                tmp='0'+(a[i]+((b[j]-'0'+carry)%2)-'0')%2;
                if(a[i]-'0'+b[j]-'0'+carry>=2) carry=1;
                else carry=0;
                a[i]=tmp;
                j--;
            }
            if(carry==1) 
            {
                a='1'+a;
            }
            return a;
        }
    };

  • 0
    R

    I really like the way you managed how the first parameter is always of greater length using recursion.


  • 0

    swap(a, b) is shorter and faster, though (constant time).


Log in to reply
 

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