LeetCode 67. Add Binary Solution Explained - Java
ฝัง
- เผยแพร่เมื่อ 4 ต.ค. 2024
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering
Thank you for taking the time to explain binary with addition examples - very helpful!!
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.
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.
You are awesome Nick...Thank you for explaining each and every problem....It is helping me a lot to improve my coding and thinking skills.....Thanks, Love from India!!!
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) ?
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.
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();
}
}
Honestly the best explanation for this problem on the platform. Thank you :D
thank you Nick.....explanation and looks both are on top level
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'
!...
Best explanation 😊
Thank you
what a nice solution and approach man thanks a ton nick brother. keep making such videos.
Very Nice Solution, Thanks a lot.
One question: why use a StringBuilder instead of a normal string?
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
It was very helpful. Thank you.
carry ==1 also should be included in while loop condition!!
question: why does '1' - '0' = 1 while '1' + '0' = 97?
The reason behind this lies in the way programming languages handle different types of data. When you use the '1' - '0' operation, many programming languages will implicitly convert the characters '1' and '0' into their corresponding ASCII (or Unicode) values before performing the subtraction.
In ASCII, the character '1' has a decimal value of 49, and the character '0' has a decimal value of 48. So, '1' - '0' essentially becomes 49 - 48, resulting in 1.
However, when you use the '1' + '0' operation, the programming language treats the '1' and '0' as characters to concatenate rather than numbers to add. In ASCII, '1' has a decimal value of 49, and '0' has a decimal value of 48. When you add these characters together, it concatenates them, resulting in the string '10', which in ASCII would represent the character with a decimal value of 97.
very good explanation
Can you do it without using the + operator (only using bit manipulation). FANG has been known to ask this
how about Subtraction ?
simply awesome
in case of 11 +11 3 % 2 =0 which will append 0 but 3 in binary is 11 should append 1
mod operator gives the remainder and when 3 is divided by 2 the remainder is 1 not 0
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();
}
}
Why did you initialize the sum as carry??
If I am understanding properly, it is because each time an operation takes place, the carry needs to be sent to sum, for the next operation. So if 1+1 happens, carry would be assigned the value of 2/2, which is 1, and once it loops back, 1 is already assigned to sum because that 1 came from the carry
Thank you
pls solve this
write 1 to 5 in binary numbers
pls solve it through java coding
Thanks for the solution. You explained it nicely. What is the space and time complexity of this solution?
The time complexity is o(n) and space complexity is o(1)
@@weizhou4974 Can you please explain that why exactly he used string builder?
@@stayblessed4real I think it's because the method needs to be returned as a string
String builder was used for 2 reasons: 1. being able to modify the String, as usual String is immutable object, 2. which also goes back to reason number, which is the reverse function.
Tnx
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');
to make it as integer, we do that
in case someone still wonders about this... When using characters in a int type variable (such as sum), they are returned with the ASCII value.
a.charAt(1)=49 (ASCII value of 1).
So if we want to get the int value of 1 we need to substract the ASCII value of 0 (48).
(int) 1-0 = (ASCII) 49-48 = 1
(int) 2-0= (ASCII) 50-48=2
…
@@franperez6454 thank you
0:08 system failure
Nice!
public static String addBinary(String a, String b){
BigInteger firstNum = new BigInteger(a, 2);
BigInteger secondNum = new BigInteger(b, 2);
BigInteger sum = firstNum.add(secondNum);
return sum.toString(2);
}
consider editing