Leetcode 29 - Bit Manipulation | Divide Two Integers
Vložit
- čas přidán 29. 07. 2024
- Topic: Bit Manipulation
Code:
github.com/Nideesh1/Algo/blob...
Leetcode:
leetcode.com/problems/divide-...
Note I claim no rights to this question. All rights belong to Leetcode. If I'm reviewing a solution that was from another Leetcode user or Leetcode itself I will give credit below.
Credit to : Leetcode User lee215 | leetcode.com/problems/divide-...
Hey there! Just wanted to let you know that some of the below links in this video description are affiliate links, which means that if you make a purchase through them, I may earn a small commission. Don't worry though, it doesn't cost you anything extra and it helps support this channel so I can continue to make more videos for you. Thank you so much for your support, and as always, all opinions are my own!
Start getting great at system design: bytebytego.com?fpr=nideesh (affiliate link)
Handpicked Algorithms and Data Structures for Interview To Save Time: interviewpen.com/?via=nideesh
Didn't expect that accent when seeing that thumbnail
xD
Indians teach all of us
My initial approach to solve this LC question, derived from repeated substraction(but in my mind, i had a feeling as this would take long amount time, if say dividend is closer to Integer.MAX_VALUE), but anyways I continued with my solution, started submitting on leetcode console. At this point i started handling the negative divisior or divisor possibilities and even the finest edge case of Integer.MIN_VALUE as dividend. But as always, for one such input my solution timed out.
With low lying head, i headed towards the discussions tab and found soln by lee215. I attempted to understand his solution but failed. Later bumped into your video in one of the comments.
Hats off man, you explained really smooth.
I like your calmness in most of your vids and your approach to gather intuition is very rare among all interview-algo-youtubers.
Keep grinding
Thanks Srinish. Yeah lee215 is very good!
Amazingly explained! The first two minutes are itself enough to get the solution clear.. Thank you so much.
My pleasure Srishti
That was a really succinct yet comprehensive explanation - thanks! Just subscribed!
dividend = 2147483647
divisor = 1
there may be an overflow for "while (a - (b
@NiddeshTerapalli Can you please comment on this ?
Hey that was a really nice explanation.
I was wondering about the edge case where dividend is INT_MIN but divisor is not -1.
In that case, the code would simply take Math.abs over dividend and divisor and proceed, but abs(INT_MIN) would again overflow, leading to a potential issue.
Am I missing something here ?
PS: I saw a previous comment of yours where you explained how its handled in Java. I am using Cpp though. Is it handled the same way there too ? I tried with a cout
Good work! explained it well, with examples during the video. Keep on!
well I would say I was able to solve this question in a competitive programming arena using this video so its good.
in inner while loop
why there is b
can you please explain the time complexity how O(log n^2)?
Thank you so much for this, I watched a number of videos but they confused me even more. First 2 min of your video I got the approach, also the way you explained your code is also very simple & understandable.
Can you explain the intuition behind the multiplication by 2? Or do you just take it for what it is and hope it magically come up to you next time you try to solve the problem?
I just realized that his explanation was wrong for the doubling
hi i am a first INFT student and i wasn't sure how to do this sum but after you explained it got easier thank u
Very clear and concise explanation . Thank you .
Well, I tried many sites to understand this concept, but I did not get them. But after seeing this video I completely understood the solution.
Thank you so much!
my pleasure
Well Explained, Thank you
This is so clear, thank you
You're welcome
That was a really succinct yet comprehensive explanation - thanks! Just subscribed! + 1
one of the best explanation I have got, thanks a lot mam. It was really amazing one
Very nice explanation. Thanks a lot!
Nicely explained. Thank you Nideesh.
You were looking nervous but good work, best explanation video for the topic imo.
Hey there! Just wanted to let you know that some of the links in this comment are affiliate links, which means that if you make a purchase through them, I may earn a small commission. Don't worry though, it doesn't cost you anything extra and it helps support this channel so I can continue to make more videos for you. Thank you so much for your support, and as always, all opinions are my own!
Start getting great at system design: bytebytego.com?fpr=nideesh (affiliate link)
Handpicked Algorithms and Data Structures for Interview To Save Time: interviewpen.com/?via=nideesh
I couldn't find a good explanation for the shifting the divisor logic, but I'm glad I found your video
Hope it was useful knyto2
Please tell the time complexity of this solution
You are awesome..please keep posting good content
Very nice explanation! Thanks!
Very short and accurate explanation sir
When the input are 2147483647
and 1, this solution wont work as b
Thanks a lot for the clear explanation !
welcome
I don't understand why the edge case
See I convert -2^32 to abs and store it in a long int
Like long int x = labs(dividend)
Continue the whole division
The place where I'm storing the ans is also long
So, I am not giving it a scope to overflow
Yet, I don't understand why after the while loops, the ans turns out -2^32
While it has to be +2^32-- because of the usage of labs and long
Why is it not working!?!
In my mind it should!!
Great solution! What is the time complexity of this solution?
Excellent explanation
Thank u for clear explanation
Great thanks for such clear explanation
You're welcome Sidhanta
Your videos are very good. Your voice make it better. I like your voice.
Very clear explanation, thx!
You're welcome!
what happens when a = 2147483647 & b = 2 (10 in binary)
I found out that a - (b
Hi so when a = 2147483647 & b = 2 then expression a - (b
thanks bro, just got the solution after 1:30 minute watching this video
How does abs(INT_MIN) fit in int?
it doesn't so returns same INT_MIN
Thanks for excellent explanation!
Thank you
Thanks for this!
what is res?
Good explanation king
Your channel is amazing
Thank you, @Nideesh Terapalli for the video. I think an edge case with negatives is not covered in the final return. Return positive result when either both dividend and divisor are greater than or equal to 0 or less than 0 i.e. it should look something like
"return (dividend >= 0 && divisor >= 0) || (dividend < 0 && divisor < 0) ? result : -1 * result;
jayshekar harkar yes your return logic looks correct
@@NideeshTerapalli it should be xor instead of or
Hi Thank you so much for that amazing explanation. There is something that I'd like to ask... Why don't we write " while( a-(b
Hi Youmna you're very welcome.
So when I ran the code with :
int x = 1;
while( a - (b = 0){
x++;
}
For an input of: 10(dividend), 3 ( divisor) i'm getting an output of 2 (quotient) which is different from the expected result of 3. This happening because x is getting incremented to 2. When x is incremented to 2 and we shift b, by doing b
@@NideeshTerapalli Aha great, I have been trying to understand this for so long. Thank you so much !
@@NideeshTerapalli Thanks for the explanation, was confused at this part.
thanks a lot bro. keep posting more videos.
Thanks for you encouragement!
Hey, nice video... keep it up with the great work. I will be subscribing.
Thank you
Nice explanation!
Impressive! Thanks. Can you by any chance guide on how to find the time complexity of this solution? Thanks!
Good question. I hadn't thought of that till now. But let me try to deduce how lee215's solution has a O (log (n^2)) time complexity.
Let's say for example, we had an array of length n.
A doubly nested for loop that looks like the following would have a time complexity of O(n^2):
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
//...
}
}
Similarly, the code I'm running is doing the following:
Let's say a is 100, b is 2,4,8,16,32,64, stopping before 100.
while( a - (b
Thanks!
Best explanation
Could you please explain a bit about how the solution works? I am confused about:
int a = Math.abs(dividend);
int b = Math.abs(divisor);
The result of a is possible overflow, for example, dividend = Integer.MIN_VALUE.
Sure let me explain. There is only 1 overflow case we have to worry about when dividend is Integer.MIN_VALUE. This happens when divisor is -1. I drew this in the video as the edge case.
When dividend is -2147483648 and divisor is -1, then quotient should theoretically be 2147483648. However is not possible as Integer.MAX_VALUE is 2147483647 then we have overflow. The code that takes care of this is
if(dividend == Integer.MIN_VALUE && divisor == -1){
return Integer.MAX_VALUE;
}
In any other case, the quotient will not overflow. If divisor is 1, then quotient will be dividend itself. If divisor has an absolute value greater than 1, quotient will not overflow.
Examples:
-2147483648 / -1 => Edge case
-2147483648 / 1 => Integer.MIN_VALUE
-2147483648 / 2 => 1073741824
-2147483648 / 2 => -1073741824
I am taking Math.abs() for dividend and divisor because I want to do division without worrying about the sign of the numbers and work with their absolute values. At the end, I return the quotient positive or negative
@@NideeshTerapalli Hi, thanks for the quick response and also the detailed answer. I understood the purpose of using Math.abs(), but you haven't explained how to handle this case: Math.abs(-2147483648) = -2147483648. Obviously, the result is an overflow. I think it's related to some kind of Bit manipulation, but I don't quite understand. Could you share your thoughts?
@@xiaojunli8704 I have spend some time and figured out why this should work with -2^31. The point is we expect that Math.abs(-2147483648) returning 2147483648 and this is exactly what happening if we are looking at bits of int. 2147483648 in binary representation is 1 and 31 zeros after and this is how Integer.MIN_VALUE looks in java, just leading 1 is a sign of number. And since we working with bits here, algorithm is correct.
@@v.yundin Thank you, I think you answered my question! In other word, we treat -2147483648 as the unsigned number of 2147483648.
@@xiaojunli8704 Hey sorry about that I didn't check your follow up comment till today. I guess I misunderstood what you were asking.
@Vladislav Yundin thanks for explaining it in such a clear way. I'll elaborate a bit on what Vlad is saying.
We know that Math.abs(-2147483648) should return 2147483648.
In regular binary 2147483648 is represented as 10 00000 00000 00000 00000 00000 00000.
However, when Java sees this, it will see that there is a most significant bit 1. And see that it is looking at a negative number. This is because java takes 'int' in two's complement. Hence, Math.abs(-2147483648) = -2147483648.
"int: Int data type is a 32-bit signed two's complement integer"
-stackoverflow.com/questions/13422259/how-are-integers-internally-represented-at-a-bit-level-in-java
P.S. I think I should start a twitter or something so people can tweet me directly their questions/clarifications. CZcams doesn't show me all the notifications
great explanation
nice solution + nice watch :P
It is giving TLE on while( a - (b
The same error is showing in my case also. Did you able to correct that error?
why you left shifted x by 1 before adding it to res?
Yeah so let's look at this part of the code:
int x = 0
while( a - (b
Thanks a lot for this clear explanation!
As the abs of INT_MIN is INT_MIN i.e. abs(-2147483648) = -2147483648, it will create a problem in the following scenario.
Dividend: -2147483648
Divisor: -10000000
In the above case, your code won't return anything. It will throw TLE though the correct output should be 124.
Should we handle this case separately?
This program handles your scenario(C++):
int divide(int dividend, int divisor)
{
if(dividend==INT_MIN && divisor==-1)
return INT_MAX;
if(dividend==INT_MIN && divisor==1)
return INT_MIN;
long a=abs(dividend);
long b=abs(divisor);
int result=0;
while((a-b)>=0)
{
int x=0; //for shifting the bit to left
while(x
Nice explaining dude, please keep posting videos.
@@sandeeppattanayak5131 lel
I was wondering about the edge case where dividend is INT_MIN but divisor is not -1.
In that case, the code would simply take Math.abs over dividend and divisor and proceed, but abs(INT_MIN) would again overflow, leading to a potential issue.
Am I missing something here ?
Nice explanation..!!
Great solution!! could you share TimeComplexity & Space Complexity for your solution ?
nicely done
Isn't that last line not abiding by the rules since it uses multiplication by -1 ?
I guess we could just do 0 - result so sorry kind of a dumb question lol
#solid answer. I will subscribe for more. Thanks
Since Math.abs(-2147483648) = -2147483648, could you please explain more about what will happen when the divisor is not -1? In my java, this will lead to the wrong result.
@Cynthia C Hey, so when the divisor is not -1, it could be more negative or more positive. Can you tell me the dividend/divisor combination you are using?
-2147483648 / -1 => Edge case
-2147483648 / 1 => Integer.MIN_VALUE
-2147483648 / -2 => 1073741824
-2147483648 / 2 => -1073741824
We know that Math.abs(-2147483648) should return 2147483648.
In regular binary 2147483648 is represented as 10 00000 00000 00000 00000 00000 00000.
However, when Java sees this, it will see that there is a most significant bit 1. And see that it is looking at a negative number. This is because java takes 'int' in two's complement. Hence, Math.abs(-2147483648) = -2147483648.
"int: Int data type is a 32-bit signed two's complement integer"
-stackoverflow.com/questions/13422259/how-are-integers-internally-represented-at-a-bit-level-in-java
@@NideeshTerapalli But regardless of the value of the divisor - Math.abs(-2147483648) will overflow - you've only intercepted the case where the divisor is -1
@@davidlawrence1398 Hi David. Are you referring to:
-1 * Math.abs(-2147483648) ?
it's better if you explain pseudo code. We don't want the solution we need an explanation so that we can implement it by ourselves.
Thanks
I get it when you explain it, but I couldn't come up with it on my own. :(
Bro your explanation is nice , but it gives Integer overflow error in c++.
Expected Gowardhan when I clicked, found Gordon instead.
Lmao that's hilarious
Could you please help with Leetcode 135
Sure, I'll make a video on that problem next
@@NideeshTerapalli Thanx, I would be eagerly waiting
@@akshitaggarwal7878 Hey Akshit, I made a video on 135 since you requested. Let me know if anything is unclear
czcams.com/video/ntXYNe4D8m0/video.html
Voice is not clear
please create more videos..
nice biceps
public class Solution {
public int divide(int A, int B) {
if(A == Integer.MIN_VALUE && B == -1){
return Integer.MAX_VALUE;
}
int a = Math.abs(A);
int b = Math.abs(B);
int sol = 0;
while(a - b >= 0){
int i = 0;
while(a - (b = 0){
i++;
}
sol += 1 = 0)? sol: -sol;
}
}
why I am getting an infinite loop in this and why math.abs is not working in java, I have tracked using the debugger and they show a's original value if we take A as negative.
Hi Nideesh, Good video. However you really really need to be a bit loud. :)
Yeah Jolly, I have a different mic in my new videos
Since, we are failing at b
java code that does not use multiplication , division , modulo ANYWHERE :)
class Solution {
public int divide(int a, int b) {
if(a==Integer.MIN_VALUE&&b==-1) return Integer.MAX_VALUE;
boolean negative = false;
boolean positive = false;
if(a0) positive = true;
else negative = true;
int result = 0;
if(a
Improved your logic a bit, the code runs faster (for C++):
int divide(int dividend, int divisor)
{
if(dividend==INT_MIN && divisor==-1)
return INT_MAX;
if(dividend==INT_MIN && divisor==1)
return INT_MIN;
long a=abs(dividend);
long b=abs(divisor);
int result=0;
while((a-b)>=0)
{
int x=0; //for shifting the bit to left
while(x
thanks Kumar
looking indian accent american
It's never clear why you decided on multiplying by a magic number 2. Clearly, you crammed the solution and just let it out here instead of building it up logically. This is a shi**y problem anyway, it has nothing to do with programming.
bhai why are you faking your accent ? Use your normal accent