Number of 1 Bits - Leetcode 191 - Python

0:00 - Read the problem
1:10 - Explain Solution #1
4:33 - Coding Solution #1
5:40 - Explain Solution #2
11:03 - Coding Solution #2

leetcode 191

#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[rishabhjain]

Great video as always. Another solution for people who prefer shift operator over mod. Cheers!

class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
for _ in range(32):
if n & 1 == 1:
count += 1
n = n >> 1
return count

[ocoocososococosooooosoococoso]

I love this channel so much. He explains so well in an easy way and with concise drawing. To me, it's really easy to follow what he saying and understand at the same time.

[dorondavid]

Great explanation of both approaches, I learned something new, thanks!

[dm]

Your speech delivery skills are great. Subscribed 👍

[lucaswang]

More general solution: (works in C, C++, Java, JavaScript)

class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
while n != 0:
# n & -n means get the rightmost 1
# n ^= (n & -n) means remove that rightmost 1
n ^= (n & -n)
count += 1
return count

[icecloud]

Should we be learning how to solve this with bit manipulation operations? I solved this initially just using prebuilt functions (converting to binary strings, replace 0 with "", return the length of the string)

[MuazAtik]

Thank you 👍👍
The First approach is causing infinite loop for the Negative numbers.
The fixed code in Java:

int hw = 0;
while (n != 0) { // != 0 instead of > 0
hw += n & 1; // & 1 instead of % 2
n = n >>> 1; // >>> instead of >>
}
return hw;

Every feedback is welcome

[omarsameh]

I turned the input into an integer and carried out normal conversion to binary to count the ones, ended up being faster than 89.30 % and less memory that 70 %.
The code is messy but it works xD

[ColinVanWinkle-xymx]

Another solution I came up with was after doing n = n>>1 each iteration, if the old value is (2*n) + 1, then you know a 1 dropped off the end, if the old value is (2*n). However I do like the logical and solution the best

[rock_]

This explaination of n & n -1 forced me to subscribe your channel. Thank you so much.😊

[rijumondal]

Loved the art for the second solution, Algorithms are the only thing that make me smile nowadays

[gouravkolhatkar]

Awesome explanation, keep it up bro <3

[lch]

So brilliant!!!! especially for the second solution.

[andrewchen]

This is so smart. I re-watched this video and it still helps me a lot. Thank you!

[WoWUndad]

Thanks this really helps for my full stack react interviews and job very applicable

[hdpasdlol]

Runtime 13ms - Beats 69.79%
Memory 11.54 MB - Beats 67.62%

class Solution(object):
def hammingWeight(self, n):
n = Counter(bin(n))

return n.get('1')

[tinymurky]

the second method can just use n&1 to get the ending bit is 1 or 0

class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
while n:
count += (n & 1)
n = n >> 1
return count

[anonlegion]

The second one is pretty smart. Thank you for the videos

[MrRenaissance]

I got an alternative solution:

class MyalternativeSolution:

def hammingWeight(self, n: int) -> int:
n = str(bin(n))
count = 0
for i in n:
if i == '1':
count +=1
return count

[krugerbrent]

This was super helpful. I was breaking my head over this bit manipulation trick when I read it on Leetcode, and I ended up here at Neetcode 😂
But at 4:25 you mentioned, we could stop the iteration because it was 0 and all the rest of them would be zero. How do we know that? If that's the case, won't we stop at the step before, where we already found a 0 -> `10`?

And at 8:55, why aren't you flipping the entire number initially and adding 1 to it like this

Also, the first approach, taking mod and adding - doesn't seem to work in Java, but yes, good solution in python.