Leetcode 29 - Bit Manipulation | Divide Two Integers

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

[@saideepesh6036]

Didn't expect that accent when seeing that thumbnail

[@user-co6rg9jt9x]

xD

[@user-bl5qv3jy1l]

Indians teach all of us

[@saurabhchaturvediscientist]

That was a really succinct yet comprehensive explanation - thanks! Just subscribed!

[@srinish1993]

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

[@NideeshTerapalli]

Thanks Srinish. Yeah lee215 is very good!

[@bellydancingwithsrishticho7245]

Amazingly explained! The first two minutes are itself enough to get the solution clear.. Thank you so much.

[@NideeshTerapalli]

My pleasure Srishti

[@Lioran90]

Good work! explained it well, with examples during the video. Keep on!

[@vyomyadav6497]

You were looking nervous but good work, best explanation video for the topic imo.

[@Veronica-vq5iz]

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.

[@zr60]

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?

[@zr60]

I just realized that his explanation was wrong for the doubling

[@anuj-ut9fo]

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

[@priyanshuagarwal5571]

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!

[@NideeshTerapalli]

my pleasure

[@theunknownguy354]

That was a really succinct yet comprehensive explanation - thanks! Just subscribed! + 1

[@techgamer4291]

Very clear and concise explanation . Thank you .

[@challasaikiran]

Nicely explained. Thank you Nideesh.

[@sandeeppattanayak5131]

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

[@partheshsoni6421]

Very nice explanation. Thanks a lot!

[@abhitripathi]

Well Explained, Thank you

[@dimpleshah6538]

Very nice explanation! Thanks!

[@vishalmishra1937]

in inner while loop why there is b

[@phaniaditya6020]

You are awesome..please keep posting good content

[@shen8015]

dividend = 2147483647 divisor = 1 there may be an overflow for "while (a - (b

[@NarenRSKumar]

@NiddeshTerapalli Can you please comment on this ?

[@PrafulPrasad]

well I would say I was able to solve this question in a competitive programming arena using this video so its good.

[@parassetia4964]

one of the best explanation I have got, thanks a lot mam. It was really amazing one

[@knyto2]

I couldn't find a good explanation for the shifting the divisor logic, but I'm glad I found your video

[@NideeshTerapalli]

Hope it was useful knyto2

[@vidyamc4340]

can you please explain the time complexity how O(log n^2)?

[@jianwenliu458]

This is so clear, thank you

[@NideeshTerapalli]

You're welcome

[@AbhishekKumar-yv6ih]

Your videos are very good. Your voice make it better. I like your voice.

[@dheerajpoonia2175]

Very short and accurate explanation sir

[@kevinjohn553]

Good explanation king

[@RA-eg8tw]

Your channel is amazing

[@abcd12272]

Great solution! What is the time complexity of this solution?

[@amit250698]

Please tell the time complexity of this solution

[@yunwang8635]

Excellent explanation

[@b747]

Hey, nice video... keep it up with the great work. I will be subscribing.

[@NideeshTerapalli]

Thank you

[@pashwajain687]

Thanks a lot for the clear explanation !

[@NideeshTerapalli]

welcome

[@naveenminhas7524]

thanks bro, just got the solution after 1:30 minute watching this video

[@NideeshTerapalli]

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

[@subramaniamseshadri9347]

Thanks for this!

[@pranjlisingh6490]

Thank u for clear explanation

[@tejas230]

Nice explanation!

[@farabikurmanshady8486]

Thanks for excellent explanation!

[@NideeshTerapalli]

Thank you

[@yuxinwu98]

Very clear explanation, thx!

[@NideeshTerapalli]

You're welcome!

[@zeus433]

what is res?

[@wukunliu1714]

nice solution + nice watch :P

[@sidhantakumarpattnaik2962]

Great thanks for such clear explanation

[@NideeshTerapalli]

You're welcome Sidhanta

[@timotheel67]

When the input are 2147483647 and 1, this solution wont work as b

[@swagatdas1991]

Nice explaining dude, please keep posting videos.

[@swagatdas1991]

@@sandeeppattanayak5131 lel

[@sandeeppattanayak5131]

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 ?

[@lalitkumarmehta6026]

thanks a lot bro. keep posting more videos.

[@NideeshTerapalli]

Thanks for you encouragement!

[@b747]

#solid answer. I will subscribe for more. Thanks

[@Sushil2874]

Nice explanation..!!

[@Chesstreamer]

great explanation

[@harshithalingapalem9268]

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!!

[@Singh11225]

what happens when a = 2147483647 & b = 2 (10 in binary) I found out that a - (b

[@NideeshTerapalli]

Hi so when a = 2147483647 & b = 2 then expression a - (b

[@BullishBuddy]

nicely done

[@rajeevsawant6350]

Great solution!! could you share TimeComplexity & Space Complexity for your solution ?

[@rudreshdixit8368]

Best explanation

[@vinnivarma1555]

How does abs(INT_MIN) fit in int?

[@kartikkesarwani1320]

it doesn't so returns same INT_MIN

[@jayshekarharkar8119]

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;

[@NideeshTerapalli]

jayshekar harkar yes your return logic looks correct

[@adishgarg5297]

@@NideeshTerapalli it should be xor instead of or

[@kunalkumarbarman9610]

Bro your explanation is nice , but it gives Integer overflow error in c++.

[@adityasinghal323]

why you left shifted x by 1 before adding it to res?

[@NideeshTerapalli]

Yeah so let's look at this part of the code: int x = 0 while( a - (b

[@adityasinghal2707]

Thanks a lot for this clear explanation!

[@lucaguarro6116]

Isn't that last line not abiding by the rules since it uses multiplication by -1 ?

[@lucaguarro6116]

I guess we could just do 0 - result so sorry kind of a dumb question lol

[@techmarcs]

Impressive! Thanks. Can you by any chance guide on how to find the time complexity of this solution? Thanks!

[@NideeshTerapalli]

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

[@techmarcs]

Thanks!

[@radoonhadoon]

It is giving TLE on while( a - (b

[@shubhamsood1406]

The same error is showing in my case also. Did you able to correct that error?

[@Animelover-ds9vg]

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

[@IsomerMashups]

I get it when you explain it, but I couldn't come up with it on my own. :(

[@youmnaelghandoor1165]

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

[@NideeshTerapalli]

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

[@youmnaelghandoor1165]

@@NideeshTerapalli Aha great, I have been trying to understand this for so long. Thank you so much !

[@lostgen36]

@@NideeshTerapalli Thanks for the explanation, was confused at this part.

[@setukumarbasak6729]

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?

[@kk.engineer]

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

[@xiaojunli8704]

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.

[@NideeshTerapalli]

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

[@xiaojunli8704]

@@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?

[@v.yundin]

​@@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.

[@xiaojunli8704]

@@v.yundin Thank you, I think you answered my question! In other word, we treat -2147483648 as the unsigned number of 2147483648.

[@NideeshTerapalli]

​@@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. KZbin doesn't show me all the notifications

[@cynthiac1968]

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.

[@NideeshTerapalli]

@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

[@davidlawrence1398]

@@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

[@NideeshTerapalli]

@@davidlawrence1398 Hi David. Are you referring to: -1 * Math.abs(-2147483648) ?

[@harveycrimsond3947]

Expected Gowardhan when I clicked, found Gordon instead.

[@NideeshTerapalli]

Lmao that's hilarious

[@mithanck4132]

Voice is not clear

[@akshitaggarwal7878]

Could you please help with Leetcode 135

[@NideeshTerapalli]

Sure, I'll make a video on that problem next

[@akshitaggarwal7878]

@@NideeshTerapalli Thanx, I would be eagerly waiting

[@NideeshTerapalli]

@@akshitaggarwal7878 Hey Akshit, I made a video on 135 since you requested. Let me know if anything is unclear kzbin.info/www/bejne/pKW7ioGbaalro5I

[@nagalakshmi1385]

please create more videos..

[@amanbhadauria2881]

nice biceps

[@jollysrivastava3326]

Hi Nideesh, Good video. However you really really need to be a bit loud. :)

[@NideeshTerapalli]

Yeah Jolly, I have a different mic in my new videos

[@setukumarbasak6729]

Since, we are failing at b

[@notinoti2552]

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.

[@LegitGamer2345]

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

[@kk.engineer]

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

[@NideeshTerapalli]

thanks Kumar

[@messi_codes]

looking indian accent american

[@abhijit-sarkar]

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.

[@fgffgf9844]

bhai why are you faking your accent ? Use your normal accent