Home » leet code » 100 Days Challenge Leetcode » Day 2 : FaceBook Asked interview Quetion :- Add Binary Sum – Java ,Python ,Cpp

Day 2 : FaceBook Asked interview Quetion :- Add Binary Sum – Java ,Python ,Cpp

If, you are preperaing for FACEBOOK Interview or will prepare. Then according to LeetCode premium it is no.4 most asked Question by Facebook as per now.

Nilesh Most important QUOTE…
#100 days of challenge leetcode
So Ladies n Gentlemen without any further due let's start,
What question saying is, Given two binary strings a and b, return their sum as a binary string.

Explanation of Approach:

Explanation summarised below:

The general idea is to add 00 to the short two strings to make them equal lengths, then traverse and calculate from the end to obtain the answer.

Let’s use an illustration to clarify: If you add 1 and 1, you’ll get 1 carried over and 0 printed. Adding 1 and 0 together gives us 1 as carry, which will print 0; Print 1 will result from adding the final remaining carry 1, which is missing a body. As a result, the answer is something like “1 0 0.”
One crucial detail is that the last addition will be 3, after which you print 1 and carry 1.

Now that we know how to conduct binary addition, let’s get into more detail. Consider the example of two decimal numbers “11” + “1,” where “11” represents “3” and “1” represents “1.”
Let’s now execute binary addition, which is quite similar to what we do with decimal addition. In decimal, we add two numbers and carry the result if it exceeds nine. Additionally, there is a number in this area with values in the decimal range of 0 to 9 and two values in the range 0 to 1. Therefore, if the result is more than 1, there is a carry; otherwise, there is no carry in binary.

I’ll demonstrate with a diagram:

  • As a result, the initial carry in the picture is “0,” and when we add 1 + 1 we obtain 2, which is greater than 1, therefore there is a carry of 1, and the outcome is 0. One plus one equals zero once more, thus we are left with a carry of one. The final carry one will be returned in its current state.
  • This binary number is therefore [22 * 1 + 21 * 0 + 20 * 0] and this is [1 0 0]’s decimal coversion, which is 4.

Now, let’s code it up:
code, each lne explained : Similar for C++, Java, Python

Pseudo Code :

Step 1:

{
//Create the result name string first. It will start out empty and serve as the answer.
        StringBuilder res = new StringBuilder(); 
        int i = a.length() - 1; // we crete i pointer for string a and we have to start adding from right to left 
        int j = b.length() - 1; // similar pointer j for string b
        int carry = 0; // we create a carry, as we have to consider it as well

Step 2:

// iterate over the loop until the both condition become false
        while(i >= 0 || j >= 0){ 
            int sum = carry; // intialise our sum with carry;
            
            // Now, we subtract by '0' to convert the numbers from a char type into an int, so we can perform operations on the numbers
            if(i >= 0) sum += a.charAt(i--) - '0';
            if(j >= 0) sum += b.charAt(j--) - '0';
            // taking carry;
            carry = sum > 1 ? 1 : 0; // getting carry depend on the quotient we get by dividing sum / 2 that will be our carry. Carry could be either 1 or 0 
			// if sum is 0 res is 1 & then carry would be 0;
            // if sum is 1 res is 1 & carry would be 0
            // if sum is 2 res is 0 & carry would be 1
            // if sum is 3 res is 1 & carry would be 1
            res.append(sum % 2); // just moduling the sum so, we can get remainder and add it into our result
        }

class Solution {
public:
    string addBinary(string a, string b) {
        string res;
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        while(i >= 0 || j >= 0){
            int sum = carry;
            if(i >= 0) sum += a[i--] - '0';
            if(j >= 0) sum += b[j--] - '0';
            carry = sum > 1 ? 1 : 0;
            res += to_string(sum % 2);
        }
        if(carry) res += to_string(carry);
        reverse(res.begin(), res.end());
        return res;
    }
};
class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        while(i >= 0 || j >= 0){
            int sum = carry;
            if(i >= 0) sum += a.charAt(i--) - '0';
            if(j >= 0) sum += b.charAt(j--) - '0';
            carry = sum > 1 ? 1 : 0;
            res.append(sum % 2);
        }
        if(carry != 0) res.append(carry);
        return res.reverse().toString();
    }
}
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        res = ""
        i, j, carry = len(a) - 1, len(b) - 1, 0
        while i >= 0 or j >= 0:
            sum = carry;
            if i >= 0 : sum += ord(a[i]) - ord('0') # ord is use to get value of ASCII character
            if j >= 0 : sum += ord(b[j]) - ord('0')
            i, j = i - 1, j - 1
            carry = 1 if sum > 1 else 0;
            res += str(sum % 2)

        if carry != 0 : res += str(carry);
        return res[::-1]

ANALYSIS :-

  • Time Complexity :- BigO(max(M, N)), M & N is the length of string a, b;
  • Space Complexity :- BigO(max(M, N)), which is the size of “res” object

Guy’s if you find this solution helpful 😊,

Leave a Reply