Sum of Two Integers - Leetcode 371 - Java
Vložit
- čas přidán 23. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
✔️ SPREADSHEET BLIND-75: docs.google.com/spreadsheets/...
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: neetcode.io/problems/sum-of-t...
0:00 - Read the problem
1:40 - Drawing Explanation
9:47 - Coding Explanation
leetcode 371
This question was identified as a microsoft interview question from here: github.com/xizhengszhang/Leet...
#microsoft #interview #java
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
ok fine, I will compromise and start doing my videos in C 😉
No please use python going forward. I religiously follow all your videos :) both for the explanation and because I like coding in python.
Why would you torture yourself like that
may be just pseudo code. lol
I'd still watch :D
Love that you completed all the vids for blind 75, but only use python for your codes. I have plenty of other people I could go to for C, so don't do any other language. Python only - that's your niche and why most people are here.
If you want to do the same thing in Python, you can use this code (and I'll explain it!):
class Solution:
def getSum(self, a: int, b: int) -> int:
mask = 0xffffffff
while b != 0:
tmp = (a & b) mask // 2:
return ~(a ^ mask)
else:
return a
To explain, the hexadecimal number 0xffffffff is the same as the binary number 0b1111111111111111111111111111111, containing 32 1's. (It's just easier to type lol.)
In order to make the code work like Java, we want to treat our numbers like they only have 32 bits. ANDing a number with the mask 0xffffffff, or 32 1's, basically turns all of a number's bits into 0's except for the rightmost 32. As a result, the number can be represented as if it only has 32 bits.
We do what Neetcode describes in his video, using XOR for the sum and AND for the carry. We AND with the mask each time we set a and b in order to keep our numbers within 32 bits.
After we exit the while loop, we have our answer a. If a is positive, then we can return it directly. However, in Python, negative numbers are represented in binary as having an unlimited number of leading 1's. The current answer would only have values in the rightmost 32 bits. Therefore, if the answer is negative, we need to convert it into Python's representation of negative numbers.
First, we need to check if the answer is negative. We cannot just check to see if the answer is less than zero because our representation of the answer is not the same as Python's (since Python's have unlimited leading 1's). We are still treating our answer as if it only fits into 32 bits.
A 32-bit signed integer is positive if the 32nd bit is a 0 and is negative if the 32nd bit is a 1. If we divide our mask (0xffffffff) by 2, we will get the binary number 0b0111111111111111111111111111111, which has 31 1's. This number is the greatest value we can have before the 32nd bit becomes a 1. Therefore, if our answer a > mask // 2, it is negative. Otherwise, it is positive and we can just return a itself.
If the number is negative, we then need to convert it into Python's representation of negative numbers. To do so, we can XOR with the mask of 32 1's in order to flip the rightmost 32 bits, since XORing a bit with 1 flips the bit. We can then NOT the number in order to turn all of the leading 0's into 1's. For example, say that the answer is -3, and (....0000000) or (....1111111) denote leading 0's or 1's until the 32nd bit:
Our representation of -3 in 32 bits: (...0000000)11111111111111111111111111111101
XOR with mask, aka flip rightmost 32 bits: (...0000000)00000000000000000000000000000010
NOT, aka flipping all bits: (...1111111)1111111111111111111111111111101
The result is Python's representation of -3, including an unlimited number of leading 1's.
Overall, the code uses the same process as Neetcode's Java code, but with masking to get numbers into 32 bits and some manipulation to get those 32-bit numbers back into Python's representation before returning.
Man how tf do u know all this stuff. My code was failing to add -8 and -12, and here I was thinking what to do with -ve integers T_T. Having a non IT background surely makes it difficult
@@eeew2691 nah, this is hard even for people with IT background :)
thank you man, i really appreciate the in depth explanation!!! this forced me to learn a little more about python today lol, i don't ever think about how integers are stored in languages and stuff so this was kind of cool to dive into.
Is there a simpler solution for Python? If not, does this mean that Python is not good for handling binary operation?
@@lingzi6599 Unfortunately, since Python stores its integers in a different way than Java, all of this solution's parts are necessary. Python is as capable as any other language for handling binary operations, but in interviews (and beyond) it can be important to remember that Python represents its integers as having more than 32 bits. In many problems, remembering the bitmask of 0xffffffff can save you if you choose to use Python!
Thanks man for this. Just finished watching all your videos on the blind 75 list, I've learnt a lot.
Thanks so much! You were the only one capable to clear in my mind these bitwise operations handled together. The use of the variable 'tmp', explaining its reason and its location on the code really clarified everything. Congrats for this awesome tutorial. God bless you. 🥰
Please use python too in your future vids! There are many java based channels, but yours is the only good python channel that I could find
@@caaarbz so is python, with ml and ai python will become top 2 soon
@@gunahawk6893 What ?, its already the 2nd most popular only behind javascript
@@NK-fe3md thats cool tho
9:31 Thanks for mentioning this. So that's why my python solution doesn't handle negative numbers.
Thank you so much for such a clear explanation! Very helpful!
this is more than hard question and you have explained it in more than easy way . thanks
Thank you really! Your course is the best of all😃
How come if I use this solution in Python I get a Time Limit Exceeded error but it runs just fine with Java?
Thank man I read your code easily, I dont have a problem with java, but do you have a solution in python for negative numbers?
This is fantastic. Now I can save the world without using any "+". ; )
I code in java. But I first come to Neetcode, listen to your explanation, go back and code in Java. My fav youtuber !
Wow! such an awesome explanation
Hey man love your videos, your explanation is absolutely spot on: the default int val in python is too big.
For people crying about python, mask to limit int size to 32bit (0xffffffff). Don't spread hate people :) cheers
class Solution:
def getSum(self, a: int, b: int) -> int:
mask=0xffffffff
while b & mask:
a, b = (a ^ b), (a & b) 0 else a
hi! in what case will b be more than 0 for your return statement? dont really get the return statement and would appreciate if you could explain!
Is the microsoft logo at the beginning just random? Or is this problem tagged for microsoft?
Thanks for Explanation.....this code will work in Java but not worked same in C++ with negative number 🙃For C++ code--------
int getSum(int a, int b) {
while(b!=0)
{
unsigned int temp=(a&b);
a=a^b;
b=(int)(temp
Thanks
why dosent it directly work in C++?
Thanks bro!!!
The best explanation EVER!
Umm... I think I found out why Neet used Java. I converted it to Python but I got a time-limit exceed error. I guess Java automatically handles some of the edge cases (like when the input is a negative number ) :/ .
Beautiful explanation
Thanks a lot!
Helpful, thank you!
your are one of best teacher out there
Nice, I was making the 1and 1 case too complicated
Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thanks man pt. 1
excellent explaination
man, your explanations are the best out there in youtube.
@NeetCode, can you please post the python solution? I tried converting your C solution to python but got a time limit exceeded error :(
There was a good reason to do this solution in java...
def getSum(self, a: int, b: int) -> int:
mask = 0xFFFFFFFF
while b != 0:
tmp = (a & b)
@@katearcher8881 Thanks!!
@@katearcher8881 Thanks! Never would've guessed this. Wow.
thanks neetcode
nice & Thank you!!
I prefer the Java because it’s more similar to other languages. Either way thanks for this great video
Please continue with python
Is it cheeky to just create list = [a, b] and then return sum(list)? (It worked as a solution)
return Integer.sum(a,b); also works in a pinch! Java
ha!
Thank you
why python give time limit exceeded?
java content from neetcode yes please
Have you done division of two integers
thanks buddy
can you explain why Python is not ideal for solving this binary question? Loved your logical approach and explanation in this video
I tried implementing the same method in python. Doesnt work for -ve numbers. The guy explain it at 9:31
Yeah, his logical approach rather than an emotional approach is quite good . lol.
best explanation
doesn't work for all test cases on python
why is the time complexity O(1)
Lol I like seeing everyone complain about this being Java...People, I'm a C++/C# programmer and I watch his Python videos.
It's not hard to convert one language to another...the point of these vids is to understand the algorithm and apply it!
Yup its not hard, but as he mentioned you can't implement the algorithm that he show in the video in python.
I also code in java but I can easily understand c++/c and not to mention I'm here so I probably understand python too. It's not that difficult after some time you just start understanding them for some unknown reason (a good unknown reason).
Try implementing this code in c/c++ then come back .
people are complaining because he chose the easy way out of this. and didn't wrote the code in c/c++.
@@rhl_ What lol
C++ was MADE for bit-shifting
Do you even know how C++ works?
@@dorondavid4698 ayyo never said cpp wasn't made for bit masking. Handling -ve number during bit operation is difficult in CPP. If u r so confident in ur coding skills , convert the code to CPP and run it for -ve number 👀.
this problem is crazy
whats funny is that before he made the temp variable, the code subtracts b from a
like this:
def getSum(a, b):
while b != 0:
a = a^b
b = (a&b)
It does not work for -1 and 1
Doesn't work for c and c++
Great explaination, but it doesn't work in C++. need additional change. See below comment of Akhilesh Sonkar for the solution
You actually listened and coded in java🥺 Thanks man. Also I see so many requests to stick to python I hope you do what you feel right I am okay with any of the language because your explanation does the work for me💯
He used Java because it's difficult to solve in Python LOL
Finally a Java vid from you. Thanks for the vid though the time complexity can't be just O(1) right?
my solution in python, use log instead of binary:
def getSum(self, a: int, b: int) -> int:
# check one is zero and other is positive
if min(a,b) == 0:
return max(a,b)
# if one is zero and other is negative
if max(a,b) == 0:
return min(a,b)
# use property of ln, ln e^x = x
x = math.e**a
y = math.e**b
z = x*y
return int(math.log(z))
class Solution:
def getSum(self, a: int, b: int) -> int:
return sum([a,b])
This code is faster than sum operator. Then why not to just use this for sum instead?
Doesn't work for negative integers, since left shift operator on negative integers is not standardized and would give different answers based on compiler.
+1. It works for Java though.
for what it's worth, the problem itself should be hard, not because it's harder than the actual hard problem, but it's not medium either
Brother please just use python
Why is this problem on Blind 75? How does knowing how to solve it help solve other questions?
If you need to work with bit or low level things this would be helpful
LeetCode's official solution says that this is a popular question at Facebook and the creator of the Blind 75 list was a Facebook tech lead. That's probably one reason why it's on the list.
It's also a tricky bit manipulation problem so it can help solidify your skills there. Since it's an annoying problem it's better to do it now than see it for the time in an interview.
lol'd when I saw the dislike. I also did the same for that question
How the hell this is marked as a medium? It’s easier than most of the “easy” ones that I’ve seen
really nicely explained!
this is the problem which you need to learn
💯
Lol you’ve thumbed down this question too and asked us to not pay attention to it
Coding in Java after coding in python for many days is too frustrating!!! So many semi-colon mistakes! Such a long method call for just print(debug purposes)..Kindly provide an alternative solution in Python too.
OR we could use logs: return int(log((e**a)*(e**b)))
Can someone please explain why I can't use sum to solve this?
class Solution:
def missingNumber(self, nums: List[int]) -> int:
#is 0 missing ?
zero_missing = 0 in nums
if not zero_missing:
return 0
tot_sum = 0
for i in range(len(nums) + 1):
tot_sum += i
arr_sum = sum(nums)
return tot_sum - arr_sum
Use whatever language you want we will still be here. Actually, I am a Java programmer. I didn't even know p of python but Neetcode is the only channel I watch for coding concepts. Most people don't understand programming languages are not important the purpose here is to understand the concept behind the questions. If you understand the concept you should be good enough to code it yourself if not then you don't know that programming language well enough. OMG, I want to write 2 pages regarding this but I think wise people will understand this.
Use Java if you want to baby! From the perspective of a beginner, the fact that this is done without an if structure is mind blasting.
why u did b != 0, can we not do a != 0?
screw this. I just used the += operator in Python and said if someone wants to ask me a bitwise question in an interview I might as well just give up
I love you
Bro no. Don't give up on us so soon :(
You used to use Python
If there are only two elements... append them into a list and do a sum on that list - Python Solution.
I ignored the "dislike" when you said so. But when I actually started doing this question i really disliked it.
congrats on the complete 75 list!!! But as a python die-heart fan~~ you bend your knees on this one? No~~ I can't accept this!!! [○･｀Д´･ ○]
😂 true , he hates java tho
Please use Python man 🥺
My career is literally dependent on your channel
Shiiiit)
Pretty bad career you got there if it's "dependent" on a rando youtube channel
I guess its a good thing to find a instructor from which you understand things the best amount
You are NOT alone! I am pretty dependent on his channel too!!! I am a college student majoring at Stat with ZERO cs background so his videos means everything to me. Plus, I code in python only.
why java :[
I am completely skipping all bit manipulation questions.
If an interviewer expects me to know this, they can get bleeped.
return a+b
few extra likes for coding in my goto language 😅
did yo u just use java coz you don't want to explain mask?
Please! I'm solely here for a python
+=
Love your dislike to the question
Please please please stick with Python...Absolutely the most interview-friendly language!!!
Please remain in Python !!!!!🙏
Keep mixing it with Java!
just look at this overly complicated code in c++ by me.... just rubbish but it works perfectly fine in the constraints defined for a and b ...............................next line
int getSum(int a, int b) {
int ans = 0;
int value = 1;
if(a < 0 && b < 0) {
a = abs(a);
b = abs(b);
value = -1;
}
if(a < 0 || b < 0) {
if(a < 0) {
if(abs(a) > b) {
value = -1;
}
else {
int t = b;
b = a;
a = t;
}
}
else {
if(abs(b) > a) {
value = -1;
int t = b;
b = a;
a = t;
}
}
a = abs(a);
b = abs(b);
int c;
int d;
int i = 0;
int e = 0;
while(a != 0 || b != 0) {
c = a&1;
a >>= 1;
d = b&1;
b >>= 1;
if(c + e - d == 0) {
ans += 0;
e = 0;
}
else if(c + e - d == 1) {
ans += pow(2, i);
}
else if(c + e - d == -1) {
ans += pow(2, i);
e = -1;
}
i++;
}
}
else {
int c;
int d;
int e = 0;
int i = 0;
while(a != 0 || b != 0) {
c = a&1;
a >>= 1;
d = b&1;
b >>= 1;
if(c + d + e == 1) {
ans += pow(2, i);
e = 0;
}
else if(c + d + e == 2) {
if(a == 0 && b == 0) {
ans += pow(2, i+1);
}
e = 1;
}
else if(c + d + e == 3) {
if(a == 0 && b == 0) {
ans += pow(2, i);
ans += pow(2, i+1);
}
else {
e = 1;
ans += pow(2, i);
}
}
i++;
}
}
return ans*value;
}
lol neatcode disliked this questino
People crying for python are going to be bad developers. It should be easy as f to port the solution in any language of your choice. I don't even understand python and I've been porting all solutions to C++ from this channel.
People complain because they can't move to another language just for one problem
Also if u convert this solution to python it would give tle
Normally I might agree with you but believe it or not sometimes the language does make a difference. This problem is quite a bit trickier in Python because integers have unlimited bit precision. It's not a simple port. To get the two's complement representation of a negative number you normally want to know how many bits your integer is.
This problem is stupid af
lol, dislike +1
python solution:
return(add(a, b))
I feel like this is too easy though even though this was accepted