LeetCode 67. Add Binary Solution Explained - Java

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[destodorova]

Thank you for taking the time to explain binary with addition examples - very helpful!!

[curiosity]

Very helpful video, but if we dont use carry variable in this program instead after sb.append(sum%2) line we can use sum=sum/2; and after while loop check if sum!=0 if true append it and then returning it will result in 1ms of runtime which is faster than 100% of java code.

[iugaialeksei]

You are awesome man, so simple and clear explanation for leetcode tasks I've ever seen on youtube. Also, your solutions are always simple and clean.

[darod]

Inserting at the end and then reversing is actually better than inserting at the beginning of the string builder with something like sb.insert(0, sum %2) ?

[dev-skills]

Below is the solution using Bit Manipulation (same Time Complexity but more space efficient)

class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1;
int j = b.length() - 1;

StringBuilder result = new StringBuilder();
boolean carry = false;

while(i >= 0 || j >= 0) {
boolean sumWithCarry = false;
boolean aBit = (i >= 0) ? (a.charAt(i--) - '0' > 0) : false;
boolean bBit = (j >= 0) ? (b.charAt(j--) - '0' > 0) : false;

boolean sum = aBit ^ bBit; // a ^ b

sumWithCarry = sum ^ carry; // a ^ b ^ c
carry = (aBit & bBit) | (sum & carry); // a & b | sum & c

if (sumWithCarry)
result.insert(0, 1);
else
result.insert(0, 0);
}

if (carry)
{
result.insert(0, 1);
}

return result.toString();
}
}

[leezhenjian]

Hi Nick, thanks for the clear explanation. I was having trouble figuring out how the carry and sum modulus works until i watched ur video.

[ashisenchoudhury]

You are awesome Nick...Thank you for explaining each and every problem....It is helping me a lot to improve my coding and thinking Love from India!!!

[RyanMcCoy-ph]

Honestly the best explanation for this problem on the platform. Thank you :D

[nikhilpoonia]

thank you and looks both are on top level

[rohitrohilla]

i wanna tell you
i am a beginner and whenever I see your code then
There is only a line in my mind 'What a crazy code is this'
!...

[satyamgupta]

what a nice solution and approach man thanks a ton nick brother. keep making such videos.

[tasneemayham]

One question: why use a StringBuilder instead of a normal string?

[mohkh]

I am a bit confused, let's say the numbers are "11" & "11" Won't the sum add 1 from each first number of these numbers to become 2 then carry is divided by 2, and then sum = carry sum =1 then sum+=1 twice to become 3? I think I perceived something wrongly because I don't think the sum should be 3. or maybe it should be 3 but I don't know how

[varunrao]

Can you do it without using the + operator (only using bit manipulation). FANG has been known to ask this

[kabilanm]

carry ==1 also should be included in while loop condition!!

[SHSelect]

question: why does '1' - '0' = 1 while '1' + '0' = 97?

[cengprog]

For anyone experiencing an error, here's a better code

class Solution
{
public String addBinary(String a, String b)
{
StringBuilder sb = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;

while (i >= 0 || j >= 0 || carry > 0)
{
int sum = carry;
if (i >= 0) sum += a.charAt(i--) - '0';
if (j >= 0) sum += b.charAt(j--) - '0';
sb.append(sum % 2);
carry = sum / 2;
}

return sb.reverse().toString();
}
}

[aryanjindal]

Why did you initialize the sum as carry??

[hande]

in case of 11 +11 3 % 2 =0 which will append 0 but 3 in binary is 11 should append 1

[shauryakapoor]

Can anyone explain why we do - '0' in line 11 and line 12? ( sum += a.charAt(i) - '0'); and at ( sum += b.charAt(i) - '0');