LeetCode Day 23 - Bitwise AND of Numbers Range

Показать описание

A coding interview problem for today is: return the bitwise AND of all numbers in range [L, R]. I first guessed the statement incorrectly and started explaining something unrelated :D

Subscribe for more educational videos on algorithms, coding interviews and competitive programming.

#Coding #Programming

Рекомендации по теме

Комментарии

I would love that Everytime you guess it wrong, we will end up having two problems in same video 😂

AlgoHacks

I admit it, I'm surprised by this genius simplicity, Thank you!

BedoEbied

7:24 This was the cutest part xD "I'm just saying random values"

babyyoda

I did this:

if (m == n) return m;

return rangeBitwiseAnd(m >> 1, n >> 1) << 1;

learnfromarandomguy

For the problem in the beginning of the video
We can also have a an array with prefix count of 0. And then p[L] - p[R] == 0 : return true
Else : return false
p is the prefix count array

bhaskar

while m < n:

n -= (n & -n)
return n

(-n) will return 2's complement of n
(n & -n) will return LSB of n

rohankanade

Thanks for the problem variation with ranges! I probably would have solved that using segment trees. Tackling each bit individually is a good trick; I'd have counted the number of 1s (or 0s) in an interval instead of calculating where the next 0 is though. But that's just personal preference.

davisito

thanks bro. It took me some hours to digest your solution after going through it on paper

jamjam

In every video something new i'm learning and it helps me to code well than before.

NikhilRaghav

I did this :)
{
while(left < right) right -= (right & -right);
return right;
}

aisakyunhotahai

4:45 Errichto writes three numbers
m = 10101
someother number(let's assume t) = 10101
n = 10101 10101001101

Now the only issue is that t doesn't lie between m and n, it is in fact smaller than m. The solution works though, and that's because the first mismatch bit is going to be zero in the answer(and hence we should assume the first mismatch bit to be 1). I think it is better to assume,
t = 10101 rather than t = 10101 because now it will lie in the range [m, n].

azazel-oss

your way of bye bye, that's so cool. never change that

musicfan

Thank you for the video again! I was checking if numbers are equal I put 1 to the lower bit and shift both numbers right until one of the numbers is zero.

int rangeBitwiseAnd(int m, int n) {
int res = 0;
for (int bit = 1; n != 0 && m != 0; n >>>= 1, m >>>= 1, bit <<= 1) {
if (n == m && (m & 1) == 1) {
res |= bit;
}
}
return res;
}

andreykarayvansky

Educational and informative as always -- thank you!

jimwoodward

Hi errichto, love your video can you start a series of explaining and coding complex algorithms? Like lucas theorem, segment trees... It would be a gem.

yogeshdhiman

Never seen this approach, something next level

karansagar

thanks Errichto. It was beautifully explained.

nopecharon

Nice video! You will not get an all zero suffix when going from m to n. For example, from 5 to 6, 101 - 110, with common prefix 1--. Still, the presented approach works because it is enough to have a zero bit in any number, which will happen due to carries.

mrvargarobert

I solved it by right shifting numbers until they were identical or zero. The concept is the same.

ClaudioBrogliato

while left<right
right &=right-1
return right

aravintharjunan

LeetCode Day 23 - Bitwise AND of Numbers Range

LeetCode Day 23 - Bitwise AND of Numbers Range

Bitwise AND of Numbers Range - LeetCode Day 23 Challenge

LeetCode Day 23 - Bitwise AND of Numbers Range (C++) with explanation

Bitwise AND of Numbers Range (LeetCode Challenge Day 23 Question) | Programming Tutorials

Leetcode coding - Day 23 (30 day challenge) - Bitwise AND for range of numbers

Bitwise And of numbers range | Day 23 | Leetcode 30 Day Challenge | Leetcode #201

Bitwise And Of Number Range Solution Leetcode Day 23

Bitwise AND of Numbers Range | 30 day Challenge | Day 23 | (C++, Java, Python) | LeetCode #201

Daily LeetCode Challenge (Day 80): Divide Players Into Teams of Equal Skill

30 Day LeetCode Challenge - Problem 23 - Bitwise AND of Numbers Range

Bitwise AND of Numbers Range (python) - Day 23/30 Leetcode April Challenge

Leetcode Day 23 of Leetcode 30 Day Challenge: Bitwise AND of Numbers Range

LeetCode 30 Days Challenge, 23th - Bitwise AND in [m, n]

Day 23/30 Leetcode : Bitwise AND of numbers range

Day 23, Leetcode's 30 Days challenge. Bitwise AND of range of number

Bitwise AND of numbers range | Range AND query | Leetcode #201

201. Bitwise AND of Numbers Range | Remove Last Set Bit | Bit Manipulation

Day 23 - Bitwise AND of Numbers Range (30-Day LeetCoding Challenge)

Day 23 - Bitwise AND of Numbers Range

D23: Bitwise AND of Numbers Range

Bitwise AND of Numbers Range || leetcode challenge || c++ solution

LeetCode 201 | Bitwise AND of Numbers Range | Solution Explained (Java)

30 Day LeetCode Challenge - Bitwise AND of Numbers Range

LeetCode Day 19 - Search in Rotated Sorted Array