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
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.
class Solution { public: int rangeBitwiseAnd(int left, int right) { int c=0; while (left!=right) { left = left>>1; right = right>>1; ++c; } return left
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.
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
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)
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?
@@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.
@@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)
Appreciate you for making this video, despite how difficult it is to explain the topic.
The 2nd solution is so simple once you understand the bit manipulation!
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
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.
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int: while left < right: right &= right - 1 return right
Did the same thing
Neato. The intuition here is God tier.
My man If I ever Get into an MNC You will be the reason for it HATS OFF!!
hello everyone doing problem of the day
I was expecting to see the 2nd solution 1st. It makes much more sense than the 1st one.
Thanks for great solution! After I saw your answer, I immediately understood the problem.
Simply Wow! what an approach
I think the second solution is a million times more intuitive and easier to reason about
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
int c=0;
while (left!=right) {
left = left>>1;
right = right>>1;
++c;
}
return left
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.
The second solution is MUCH simpler than the first one
The 2nd solution was brilliant!
Thank you very much.
The second approach is awesome
I will save this video for a time I feel smart enough to understand it 😂
the explanation isnt good enough
tnx for explaination that was perfect
great explanation, loved it
how is the time complexity log(n) ? Can someone please explain ?
When is the more detailed version of the roadmap coming out? Just watched your video of saying you might do it, any updates?
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
That was really really clever
thank you sooo much
thanks for the video. what's your pen tablet? waccom? thanks
Damn finally i can breath easily this problem is tough for me tks neet for trying to explain
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)
Please create playlist for Grind series of problems.
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?
There is the edge case where both numbers in the range are the same.
@@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.
@@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.
@@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)
the second case is much much easier and logical
You are the goat
Cant this be done in constant time by XORing left and right to get the differing bits and just cutting them out?
uhm just a random observation
all the outputs will be in the form of 2^x, idk how to properly write it
I think the result will be a summation of 2^x, but not necessarily 2^x
Can you explain this more? I am not understanding why the solution isn't just 2^(right-left) @@NeetCodeIO
If its less than 32 --- or else its 0 ?
yeah summation of 2^x, thats the pattern@@NeetCodeIO
Can you explain the %?
well last one was intuitive
maybe would have been better to start the video with the first approach since easier to understand
Lol, my initial O(n) solution looked for biggest power of 2 within range and iterate from there
wow
Disliked the video after you explained the first solution. Then liked after seeing the last solution😂
The prefix solution feels more intuitive to my monkey brain. We just look for where the leftmost binaries become equal
couldnt understand much
I hate bitwise
jesus christ.
My brain to me: GET A LIFE
wow