Coding

LeetCode Add Binary Solution

0
(0)

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

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= a.length, b.length <= 104
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.

Solution

First of I started trying to understand the problem. We are given two strings which are representations of two binary numbers. We need to return sum of these two binary numbers in string format.

My thought process of solving this was using how we do with pen and paper. Add last two digits of the string (you have to start from the end of strings), then based on result, carry a number and add second last two digits and keep going till you finish the smaller string. Then add remaining digits of larger string with carry and keep going till you find the beginning of larger string. After that if there is carry, add carry to the result.

Things that you can keep in mind while doing binary addition.

0 + 0 = 0

1 + 0 = 1

1 + 1 = 10

1 + 1 + 1 = 11

You can see that in the first two additions, the carry will be 0 and in the last two additions carry will be 1.

Below is the java code for the same.

public String addBinary(String a, String b) {
        String small;
        String large;
        
        if (a.length()>b.length()) {
            large = a;
            small = b;
        }
        else {
            small = a;
            large = b;
        }
        
        int sLen = small.length();
        int lLen = large.length();
        int carry = 0;
        StringBuilder addn = new StringBuilder();
        for (int i=0; i<small.length(); i++) {
            char s = small.charAt(sLen-i-1);
            char l = large.charAt(lLen -i-1);
            int sInt = Character.getNumericValue(s);
            int lInt = Character.getNumericValue(l);
            int sum = sInt+lInt+carry;
            if (sum == 0) {
                addn.append(0);
                carry = 0;
            }
            else if (sum == 1) {
                addn.append(1);
                carry = 0;
            }
            else if (sum == 2) {
                addn.append(0);
                carry = 1;
            }
            else {
                addn.append(1);
                carry = 1;
            }
        }
        
        for (int i=0; i<lLen-sLen; i++) {
            char l = large.charAt(lLen-sLen-i-1);
            int lInt = Character.getNumericValue(l);
            int sum = lInt+carry;
            if (sum == 0) {
                addn.append(0);
                carry = 0;
            }
            else if (sum == 1) {
                addn.append(1);
                carry = 0;
            }
            else if (sum == 2) {
                addn.append(0);
                carry = 1;
            }
            else {
                addn.append(1);
                carry = 1;
            }
        }
        
        if (carry == 1) addn.append(1);
        
        return addn.reverse().toString();
    }

Below is how fast the solution is.

Off course you can further optimize the code to make it sleeker. Probably do that as an exercise.

Lessons learnt while solving this problem

  • While testing initially I found some test cases failing. Then I got to know I missed resetting carry variable during the loop in some conditions. I found this out during debugging the code. So it is ok to debug the code and find out where you are doing wrong. If your thought process is right, then it must be some simple mistake that you need to find using debugging in order to correct your solution.
  • In the above code I am violating DRY (Don’t Repeat Yourself) principle. See where you can find the opportunity so that you don’t repeat any code and rewrite that as a function or method and reuse that.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?