Bitwise AND of Numbers Range - Leetcode 201

Bitwise AND of Numbers Range - Leetcode 201 - Python

Рет қаралды 15,788

NeetCodeIO

Күн бұрын

Пікірлер: 59

@yang5843 11 ай бұрын

Appreciate you for making this video, despite how difficult it is to explain the topic.

@yang5843 11 ай бұрын

The 2nd solution is so simple once you understand the bit manipulation!

@siddhr6241 7 ай бұрын

I feel this video is an exception to your usual easy to understand explanations. I think it would be more concise to explain that the left and right most number would have a common prefix. The problem reduces to finding that common prefix (if any) between the left and right numbers of length 32 (and put zeros to the remaining positions), giving O(1) time complexity.

@deepmondal8459 11 ай бұрын

7:01 class Solution: def rangeBitwiseAnd(self, left: int, right: int) -> int: res = 0 for i in range(32): # Iterate over each bit position if (left >> i) & 1 and (right >> i) & 1: # Check if the i-th bit is set in both left and right mask = (1

@BlunderArmour 11 ай бұрын

Neato. The intuition here is God tier.

@jing_wang_jjang 11 ай бұрын

Thanks for great solution! After I saw your answer, I immediately understood the problem.

@electricindro2236 11 ай бұрын

The 2nd solution was brilliant!

@meetverma4812 11 ай бұрын

My man If I ever Get into an MNC You will be the reason for it HATS OFF!!

@nicolasguillenc 11 ай бұрын

I will save this video for a time I feel smart enough to understand it 😂

@tusharkumarraj6066 4 ай бұрын

the explanation isnt good enough

@udaygodaba6860 11 ай бұрын

Simply Wow! what an approach

@karthikeyansundaram6894 4 ай бұрын

Thank you very much.

@chethanhebbar4352 Ай бұрын

I really felt that the 2nd solution was more intuitive.

@markerman491 11 ай бұрын

When is the more detailed version of the roadmap coming out? Just watched your video of saying you might do it, any updates?

@Pegasus02Kr 11 ай бұрын

I think the second solution is a million times more intuitive and easier to reason about

@alphaferret1220 11 ай бұрын

hello everyone doing problem of the day

@erminiottone 11 ай бұрын

The second solution is MUCH simpler than the first one

@alnaskabeer1361 11 ай бұрын

The way i approached it was different. I realized that in order for it to have an non 0 solution, the the number of digits in the binary rep should be equal, since otherwise in order to gain an extra digit, there must be a power of 2 within the range, which obviously makes the entire thing 0. I used log2 of both of them numbers to check the digits, and then i statted at that bit and found the prefix that is common... And then returned the answer.

@GameFlife 11 ай бұрын

Damn finally i can breath easily this problem is tough for me tks neet for trying to explain

@hundred_gaming123 11 ай бұрын

class Solution: def rangeBitwiseAnd(self, left: int, right: int) -> int: while left < right: right &= right - 1 return right

@jayraval2846 11 ай бұрын

Did the same thing

@imantaheari 11 ай бұрын

tnx for explaination that was perfect

@m.kamalali 11 ай бұрын

The second approach is awesome

@thiagosdev 11 ай бұрын

That was really really clever

@jaatharsh 11 ай бұрын

great explanation, loved it

@akshayavenkatesan2912 11 ай бұрын

how is the time complexity log(n) ? Can someone please explain ?

@ALONEWILL 11 ай бұрын

thanks for the video. what's your pen tablet? waccom? thanks

@shepmax555 2 ай бұрын

I was expecting to see the 2nd solution 1st. It makes much more sense than the 1st one.

@ninjaasmoke 11 ай бұрын

class Solution { public: int rangeBitwiseAnd(int left, int right) { int c=0; while (left!=right) { left = left>>1; right = right>>1; ++c; } return left

@gauravsharma-lu4if 11 ай бұрын

thank you sooo much

@rydercasazza9745 11 ай бұрын

Cant this be done in constant time by XORing left and right to get the differing bits and just cutting them out?

@wavecheeez1246 11 күн бұрын

I never understand why we need these bit operations. Are they used anywhere in the world? I’ve never seen bit operations mentioned in any Python course, except once when I specifically searched for them.

@anthonya880 11 ай бұрын

Please create playlist for Grind series of problems.

@sri_harsha_dv 11 ай бұрын

I tried O(n) method but it doesn't work. I found similar way of doing the 2nd method in the video. Obviously the method discussed in the video is the ask but I can't figure out in terms of bit operations. I know its not good but here is my solution. bin_left,bin_right = bin(left)[2:],bin(right)[2:] if len(bin_right) > len(bin_left): return 0 def recursion(str1,str2): if str1: if str1[0] == str2[0]: return str1[0]+recursion(str1[1:],str2[1:]) else: return "0"*len(str1) else: return "" return int(recursion(bin_left,bin_right),2)

@spsc07 11 ай бұрын

uhm just a random observation all the outputs will be in the form of 2^x, idk how to properly write it

@NeetCodeIO 11 ай бұрын

I think the result will be a summation of 2^x, but not necessarily 2^x

@bleh-hc9mw 11 ай бұрын

Can you explain this more? I am not understanding why the solution isn't just 2^(right-left) @@NeetCodeIO

@bleh-hc9mw 11 ай бұрын

If its less than 32 --- or else its 0 ?

@spsc07 11 ай бұрын

yeah summation of 2^x, thats the pattern@@NeetCodeIO

@coleyab 11 ай бұрын

You are the goat

@adiesha_ 11 ай бұрын

I would argue this is a constant time algorithm, since all integers has 32 bits and this value is a constant. public int rangeBitwiseAnd(int left, int right) { int diff = right - left + 1; int digits = (int)Math.ceil((Math.log(diff)/Math.log(2))); int val = (0x7FFFFFFF

@2EOGIY 11 ай бұрын

Please let me know if I'm wrong, but the result will be the most significant bit or 0; its complexity could be reduced to O(1) just by doing AND on the most significant bit of a bigger number and filling the rest with zeroes. Am I right?

@sophiophile 11 ай бұрын

There is the edge case where both numbers in the range are the same.

@2EOGIY 11 ай бұрын

@@sophiophile good point, but adding selection does not change complexity O(1), you could say O(2) as there will be only two cases checked.

@sophiophile 11 ай бұрын

@@2EOGIY In Big O notation, you never say O(2), no matter the number of operations, as long as the number doesn't scale with input size, you say O(1) or 'constant time'. I get the point you are conveying of course, and you might be aware of what I said. But I thought I'd mention in just in case, because saying something like O(2) in a code interview would be seen as a red flag.

@2EOGIY 11 ай бұрын

@@sophiophile Thank you for pointing it out. Otherwise, I would died stupid. After research, I found: Big O - Upper Bound, Big Omega (Ω) - Lower Bound, Big Theta (Θ) - Tight Bound. So complexity can be described here as O(2), Ω(1), Θ(1)