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
@aaqibjavedz2569
10 ай бұрын
Using range(32) is good. In java was getting Time limit exceeded, fixed it with >>> operator.
@jarvis9092
4 ай бұрын
same code shorter one: class Solution: def hammingWeight(self, n: int) -> int: res=0 while n: res+=n&1 n=n>>1 return res
@ocoocososococosooooosoococoso
2 жыл бұрын
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.
@CostaKazistov
2 жыл бұрын
Being a native speaker is a massive advantage, isn't it. It's no wonder this channel exploded in popularity recently. Almost every time I search for a particular solution, it comes up top in search results. I like watching explanations to a particular Leetcode problem from few different channels. Neetcode's explanation are clearest yet that I have come across.
@user-sd8oo1fd9g
2 жыл бұрын
ㅎㅇ용
@icecloud48
2 жыл бұрын
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)
@stephanbranczyk8306
Жыл бұрын
It completely depends on the type of company you want to work with. For 99% of the companies out there, your solution should be enough. But if you want to work for a FAANG company, or a company that does low level hardware, they may expect you to know some bit manipulation also. At least, learn the the first technique shown in the video, it isn't that hard, and it can be useful for Leetcode contests. For the second technique, may be skip it for now.
@dorondavid4698
2 жыл бұрын
Great explanation of both approaches, I learned something new, thanks!
@dm4945
2 жыл бұрын
Your speech delivery skills are great. Subscribed 👍
@lucaswang8457
2 жыл бұрын
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
@akdec0092
2 жыл бұрын
My solution (Works in Python) - Based on the fact that the questions states that "The input must be a binary string of length 32.": count = 0 for i in range(32, -1, -1): if(n < 2**i): continue else: n = n - 2**i count += 1 return count
@nikhil_a01
Жыл бұрын
In what way is this a more general solution? NeetCode's second solution should work in all those languages too. It's a classic solution dating back to 1960.
@omarsameh8277
2 жыл бұрын
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
@AsifIqbalR
2 жыл бұрын
The interviewer won't like that TBH.
@namoan1216
2 жыл бұрын
@@AsifIqbalR why not?
@rock_213
2 жыл бұрын
This explaination of n & n -1 forced me to subscribe your channel. Thank you so much.😊
@rijumondal6876
7 ай бұрын
Loved the art for the second solution, Algorithms are the only thing that make me smile nowadays
@MuazAtik
6 ай бұрын
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
@ColinVanWinkle-xy7mx
Жыл бұрын
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
@gouravkolhatkar3623
2 жыл бұрын
Awesome explanation, keep it up bro
@lch99310
2 жыл бұрын
So brilliant!!!! especially for the second solution.
@WoWUndad
2 ай бұрын
Thanks this really helps for my full stack react interviews and job very applicable
@andrewchen2349
Жыл бұрын
This is so smart. I re-watched this video and it still helps me a lot. Thank you!
@dilhfvesgetg6192
Жыл бұрын
This problem is weird because they give you the input as an unsigned int. So why wouldn't i just convert it to binary, then a string and loop through it? Incrementing a counter as you go. I wish they would have specified that bit manipulation was required rather than letting you do whatever you want essentially. Great video though!
@brukts3361
Жыл бұрын
You can definitely convert it into a string, it's just a worse solution. A string is ultimately just a collection of numbers. In UTF-8, the string "1010" would be the numbers [49, 48, 49, 48]. There's a bit of work involved in converting it from the number `0` to the number `48` which we can bypass by avoiding that. It's not disallowed, just less efficient.
@Farofeiro231
10 ай бұрын
Excellent video! Thank you for this!
@anonlegion8331
8 ай бұрын
The second one is pretty smart. Thank you for the videos
@ianpan0102
2 жыл бұрын
*Laughs in Python one-liner:* return bin(n).count('1')
@MrRenaissance17
2 жыл бұрын
I've used the count function before but it increases the run time
@UKMatt32
Жыл бұрын
Would this be frowned upon by an interviewer? My solution was fairly simple, I just converted the input n into a string using "{:b}".format(n), which actually automatically removes all the zeroes anyway. Then, it just returns string.count("1"). Only two lines of code?
@nikhilaradhya4088
Ай бұрын
You are not really manipulating any bit
@cynthiawelinga8351
11 ай бұрын
this would actually be another cool way to increment count since it uses bit operators end to end for the solution count += n&1
@tinymurky7329
Жыл бұрын
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
@IK-xk7ex
2 жыл бұрын
The solution with subtracting 1 is very smart, take my like :)
@andrewsa7980
Жыл бұрын
1st method: (easy peasy) digit = 0 while n: if n % 2 == 1: digit += 1 n = n // 2 return digit
@allenvert_
2 жыл бұрын
hiii, the educative 10% doesnt work? I am trying to purchase Grokking the coding interview but I cannot apply the 10% for some reason : (
@krugerbrent4270
9 ай бұрын
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 `01111110`? Also, the first approach, taking mod and adding - doesn't seem to work in Java, but yes, good solution in python.
@praveen9083
2 жыл бұрын
It works but is not efficient as the second solution he talked about. class Solution: def hammingWeight(self, n: int) -> int: result = 0 for i in range(32): result += ((n & (1
@HotDiceMiniatures
2 жыл бұрын
incredible!
@abhinavbindra9274
2 жыл бұрын
nice solution and explanation
@danielsun716
2 жыл бұрын
why cannot we just use str() function to n, then check there are how many ' 1' in the string? I think that gonna be pretty easier. Like this, str(n), then count it. But it failed.
@MrRenaissance17
2 жыл бұрын
This is what I thought and I know why it failed because when you str(n) it reads the number as the actual number equivalent not the binary number itself. When you convert it to string use bin(n) to convert it back to it's binary equivalent then run the program. 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
@zactamzhermin1434
2 жыл бұрын
@@MrRenaissance17 `return bin(n).count("1")` is sufficient
@andriidanylov9453
Жыл бұрын
Cool. What a creative solution 😀
@asdfasyakitori8514
9 ай бұрын
Great video
@MrRenaissance17
2 жыл бұрын
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
@hippybonus
2 жыл бұрын
This solution is actually faster than all the of solutions above
@lameow76
2 жыл бұрын
Shouldn't the time complexity of first method be log(n) because shifting bits to the right is essentially same as integer division by 2, even tho we know that number of iterations won't exceed 32
@ThePiones
2 жыл бұрын
We're not dividing the "array" into the middle several time. We're simply doing the same thing 32 times. No logs here. If it was 64 bits, we'd simply do double the shifts, right? The fact that it's effectively integer division by 2 cancels out with the fact that 64 bits encodes exponentially more than 32 bits, but that's beyond the point.
@amankassahunwassie587
Жыл бұрын
That's right. I also prefer O(log n ). O(log n ) is more accurate expression than O(1), though we know the worst case is 32, O(1).
@lameow76
Жыл бұрын
@@ThePiones if you take maximum number that a 32 bit int can hold and you keep deviding it by 2 you'll notice that it will take exactly 32 iterations, not more than that. Same goes for 64bit integers
@fazlannazeem3607
2 жыл бұрын
Just wondering why the first solution's(using mod operation) time complexity isn't O(log n). We are stopping when n reaches 0 and doesn't that correspond to how many times we have to divide n to reach 0?
@ThePiones
2 жыл бұрын
We're dividing a number, not the "array". We simply need to do the same thing 32 times. If it was 64 bits, we'd do it 64 times. No logs here
@amankassahunwassie587
Жыл бұрын
That's right. it is the O(log n) but the maximum number can be represented in int is 2^32, so O(log2^32) is 32. so the worst case is 32. So that's why it's O(1) but I also prefer to say O(log n) instead of O(1). O(log n ) is more accurate expression that O(1).
@dcrock8978
Жыл бұрын
@@amankassahunwassie587you’re correct, it’s technically O(n) if the problem was to expand to a larger set of numbers, he’s just saying it’s closer to O(1) because it’s only 32 or 64 loops which is a few nanoseconds runtime.
@mr.fabulous5165
Жыл бұрын
nice effort man! But i think you might need to explain second solution really hard to you interviewer if they didn't know this solution already.
@kingwangzzangkong
2 жыл бұрын
why no need to manipulate input to binary string (integer) in your solution? I had to use format method for n to convert it to real binary string( 11 -> 00000000000000000000000000001011)
@priyankasetiya1358
Ай бұрын
class Solution { public int hammingWeight(int n) { int res=0; while(n>0){ res+=n&1; n=n>>1; } return res; } }
@bryanbocao4906
10 ай бұрын
I wanna click the like button more than ones. Thanks for your video!
@leepakshiyadav1643
2 жыл бұрын
excellent explanation :)
@mohd.tabishkhan4868
7 ай бұрын
I could think of the second solution but it could not tackle the large input size that cannot be held by the int data type in Java, nevertheless it seems like the practice is paying off.
@omarsameh8277
2 жыл бұрын
Why don't we just iterate over the input as a string and count the number of ones? Edit: nvm it doesn't work, it'll just change it into a denary number, my bad.
@trungthanhbp
2 жыл бұрын
😁
@mudd7522
2 жыл бұрын
The input is an integer. If you want to turn it into a string representation of the binary, you're going to have to do some bit manipulation regardless.
@omarsameh8277
2 жыл бұрын
@@mudd7522 in python we can just use the str() method
@VitalMercenary
2 жыл бұрын
It would be slower, I am guessing the str() method behind the scenes takes O(n) time where n is the length of the number it is converting to a string. Then you would have to iterate it again and count.
@omarsameh8277
2 жыл бұрын
@@VitalMercenary yeah it doesn't work either way my bad
@CST1992
3 ай бұрын
Leetcode basically gave you the finger by making your "more efficient" solution slower by 2 milliseconds. But yeah, it's definitely more efficient.
@nikhilaradhya4088
Ай бұрын
Doesn't bitwise and operation take O(log(n)) base 2 time?
@jst8922
Ай бұрын
Looks like lc changed examples (at least 1st one): Example 1: Input: n = 11 Output: 3 Explanation: The input binary string 1011 has a total of three set bits. Example 2: Input: n = 128 Output: 1 Explanation: The input binary string 10000000 has a total of one set bit. Example 3: Input: n = 2147483645 Output: 30 Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.
@user-xc3vp7eu7y
16 күн бұрын
lol the faster solution is 2ms slower... but great vid keep it up
@hwang1607
11 ай бұрын
definitely difficult to come up with the optimal solution by yourself
@hjufdvbjihde
4 ай бұрын
why is the time complexity of the first solution O(1) instead of O(n) when we have to run through every single bit?
@Uebagi
4 ай бұрын
Because int is always 32 bits.
@rakeshkumar098
2 ай бұрын
& this is bitwise and && This is logical and
@Fidelity_Investments
Жыл бұрын
*does the exact same thing just with &, time limit exceeded
@smtp_yurzx
Жыл бұрын
Great video, to learn about bits. This was supposed to be easy so I used regex for the solution Something like>>> def oneBits(bits): import re return len(re.sub("[^1]", "", f"{bits}"))
@pauljones9150
2 жыл бұрын
He's so passionate
@oscarply93
8 ай бұрын
as a former teacher, I love that you take the time to explain why the approach works. I feel like I am learning so much more when you do that.
@rvmelo
8 ай бұрын
it doesn't work in javascript: var hammingWeight = function(n) { let res = 0; while (n > 0) { res += n % 2; n = n >> 1; } return res; };
@Axl124124
Жыл бұрын
why don't convert the binary number to a string and loop through it. I think the time complexity would stay the same as it is still a 32 bit number we are interating through.
@mygodThatsmyShit
2 жыл бұрын
I swear to god that if one day I got FAANG jobs will donate you
@ahmedbaruwa8433
Жыл бұрын
The second solution is Brian Kernighan's algorithm
@HR-pz7ts
Жыл бұрын
I had my intuition clear but for some reason this won't work in java.
@juliagulia7384
2 жыл бұрын
I'm not sure why, but when I try to submit the brute force solution in java, the time limit always exceeds.
@joshuabump6147
2 жыл бұрын
I had the same issue
@goodday-dz7me
2 жыл бұрын
his first solution is not working for Java because of signed representation
@stephanbranczyk8306
Жыл бұрын
@@goodday-dz7me Try using while (n != 0) { instead of while (n > 0) {. Once I fixed this minor issue, my Java solution worked for signed values as well (and was able to pass the entire test suite). I bet you made the same mistake I made. :) However, even with my error, I didn't get a time limit exceeded. Julia and Joshua, I'll have to see your code to see what's wrong with it.
@KTL-rs7ge
2 жыл бұрын
so what is "Blind 75"? I've searched for it on google but I can't find the answer
@huhuboss8274
Жыл бұрын
it is his playlist with 75 problems
@toyszone7749
Жыл бұрын
Why n%10 cant work here?
@tanaypatel8412
Жыл бұрын
I have the similar query?
@target90plus69
Жыл бұрын
please make some video in indian accent
@Mahi4.t
4 ай бұрын
🤯
@AdamRubiks
Жыл бұрын
scene thane
@mahadishakkhor123
3 ай бұрын
use 1.75x speed
@akdec0092
2 жыл бұрын
My solution (Works in Python) - Based on the fact that the questions states that "The input must be a binary string of length 32.": count = 0 for i in range(32, -1, -1): if(n < 2**i): continue else: n = n - 2**i count += 1 return count
@telephon3208
Жыл бұрын
your first decision doesn’t work in kotlin with max int value: 11111111111111111111111111111101
Пікірлер: 105