213ms java solution. use two pointer to calculate. O(n) times


  • 6
    S
    public class Solution {
        public String addBinary(String a, String b) {
            StringBuilder str = new StringBuilder();
            int aPtr = a.length() - 1;
            int bPtr = b.length() - 1;
            int carry = 0;
            int count = 0;
            while(aPtr >= 0 || bPtr >= 0) {
                if(aPtr >= 0) {
                    if(a.charAt(aPtr) == '1') {
                        count ++;
                    }
                }
                if(bPtr >= 0) {
                    if(b.charAt(bPtr) == '1') {
                        count ++;
                    }
                }
                if(carry == 1) {
                    count++;
                }
                carry = (count > 1 ? 1 : 0);
                str.insert(0, ((count == 0 || count == 2)? '0' : '1'));
                count = 0;
                aPtr--;
                bPtr--;
            }
            if(carry == 1) {
                str.insert(0, '1');
            }
            return str.toString();
        }
    }

  • 0
    F

    same algorithm as mine, but your code is so neat and easy to read, thumb up!


  • 0
    S

    Thanks you, let's crush the coding!


  • 0
    Y

    str.insert(0, ((count == 0 || count == 2)? '0' : '1'));
    What if count==3?


  • 0
    S

    oh, this line is to set up the position that is not a carry, the last line has deal with the carry bit


  • 0
    S

    u can see from the expression, when count is 0 or 2, the bit set to 0, otherwise, means 1 and 3, set to 1


  • 0
    Y

    when carry=1,
    if aPtr >= 0 count++;
    then count=1
    if bPtr >= 0 count++;
    then count=2
    if(carry == 1) count++;
    then count=3


  • 0
    Y

    oh I know the reason. Thank you!


Log in to reply
 

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