The thing that I love about neetcode is how he builds our intuition. Rarely do I have to look at his actual implementation--I can just watch his explanation, understand the problem and solution, and then implement it myself.

Best leetcode channel by far. I like that you have the problem category (i.e. Dynamic Programming) in the titles.

@juliuscecilia6005

3 жыл бұрын

^

Not sure it should be graded as easy problem. Neetcode do really explain every problems in a brilliant way, love it!

Love your channel! Here's a slightly simpler solution which I came up with. The idea here is that the number of 1 bits in some num i is: 1 if the last digit of i (i % 1) is 1, plus the number of 1 bits in the other digits of i (ans[i // 2]). class Solution: def countBits(self, n: int) -> List[int]: ans = [0] * (n + 1) for i in range(1, n + 1): ans[i] = ans[i // 2] + (i & 1) return ans

@gladyouseen8160

2 жыл бұрын

Absolutely i was expecting this answer from neetcode any ways its the best python interview preparation channel

@batlin

2 жыл бұрын

Exactly how I solved it too, although I used i >> 1 instead of i // 2 in the lookup step but maybe the Python VM optimises integer division by 2 to be the same as a bit shift (even for negative numbers).

@johnlocke4695

2 жыл бұрын

Wow. How did you get the idea that (i&1) gives the remaining 1's in binary number?

@Marcelo-yp9uz

2 жыл бұрын

Yes, and you don't even need to build up the entire list beforehand, it is guaranteed that ans[i // 2] will be in the array if you are iterating from 1 to n + 1: ans = [0] -> ans.append(ans[i//2] + (i & 1))

@roynx98droid

2 жыл бұрын

Instead of i // 2 you may use i >> 1

I think the idea is good, but the dynamic programming is not very intuitive. I got this idea from your previous video on reverse bits. 0 - 0000 1 - 0001 2 - 0010 3 - 0011 4 - 0100 5 - 0101 you can see if we shift 5 to the right by 1, and it becomes 2, and 5 & 1 is 1, so the number of 1's in 5, is actually the number of 1's in 2 plus 1, because 5&1 == 1. similarly, if we shift 4 to the right by 1, which becomes 2 as well, and 4&1 is 0, so number of 1's in 4, is the the number of 1's in 2 plus 0, because 4&1 == 0. def countBits(self, n: int) -> List[int]: ans = [0]*(n+1) for i in range(1, n+1): ans[i] = ans[i>>1] + (i&1) return ans;

@8bit_hero850

2 жыл бұрын

this is more intuitive than the entire video lol.. thanks for this

@omkarbhale442

2 жыл бұрын

THank you for the explanation.

@markolainovic

Жыл бұрын

Nice!

@ningyuwhut

9 ай бұрын

genious!

@SHARMATUSHAR1_

9 ай бұрын

Yeah, this was over complicated. Watch Techdose's video. His explanation and intuition is much better. Basically, for odd one we'll add 1 to the i//2 as we lost the least significant bit which was 1 and for even we won't add 1 as the lsb was 0. Example: 5 -> 101 We do 5 >> 1 so now -> 5 becomes 10 which is 5//2 == 2. So bits in 5 = bits in 5//2 + 1 Similarly for 4 -> 100 (even) We do 4>>1 so now -> 4 becomes 10 which is 4//2 == 2. So bits in 4 = bits in 4//2 (no 1 added because we lost the 0 in the lsb) so we can say for every n bits in n = bit in n//2 (+1 if odd) code will be super simple too def countBits(self, n: int) -> List[int]: ans: List[int] = [0]*(n+1) for i in range(1, n+1): if i%2==0: ans[i] = ans[i//2] else: ans[i] = ans[i//2]+1 return ans

Great explanation. First, it seemed very hard to understand. but after watching this video I realized how to solve this problem. thank you.

9:10 Let's clean this up a tiny... bit 😏 Thank you for the amazing explanation!

Thank you for your binary questions update videos!!! Save my life

So the idea is to break down the problem i into a smaller subproblem which has already been computed. I realised there are two ways of breaking the problem down. In this video, he chopped off the leftmost bit - hence we need to keep track of the offset variable. However, we can do away offset by chopping off the rightmost bit instead of leftmost. we just need to figure out whether the chopped off bit is a 1 or 0. Essentially: chopped = i >> 1 dp[i] = dp[chopped] + (i & 1)

U a God.. Thanks for explaining the offset swell [16, 8, 4, 2, 1] - offsets from right to left visually

I'm doing these in java but still find that you have the best explanations... thanks. You truly understand the concepts whereas other KZreadrs sometimes are just reading solutions

I think it helps to write down the recursive relation fully. Basically, our "offsets" are powers of 2 that update whenever the current value n is a power of 2. I don't think this is really a DP problem, so I'll call Neetcode's dp[] array memo[]. Then we have the following recursive relation: Base case: memo[0] = 0 Inductive case: memo[n] = 1 + memo[n - 2^(floor of log_2(n))]. Then in python code this becomes ```python from math import log2 class Solution: def countBits(self, n: int) -> List[int]: memo = [0] * (n+1) for i in range(1,n+1): memo[i] = 1 + memo[i - 2**int(log2(i))] return memo ```

Simple DP using right shift & boolean &(odd/even check): vector countBits(int n) { vectorv(n+1); v[0]=0; for(int i=1;i>1]+(i&1); } return v; }

Another way to compute offset offset = 2 ** int(math.log2(i)) This works because int(log2(n)) gives the index of the most significant bit and 2 to the power of that gives the max power of 2 that we have seen so far

You are simply the best, your voice is so soothing too :P Thank you buddy, wishing you all the best

Found your video from leetcode today, Gr8 videos

I love your drawing explanation. It's easy to understand. I'd love to know what tool are you using for drawing?

This problem was hard for me to understand but I finally understand it. Essentially, we track the last power of 2 we encountered and in the array we use DP to solve for a given index doing dp[i - last power of 2 encountered]. My solution is like yours, except I make my variables more long/explicit in naming to understand the problem: dp = [0] * (n + 1) dp[0] = 0 curr_power_of_two = 1 previous_power_of_two = 0 for i in range(1, n + 1): if i == curr_power_of_two: previous_power_of_two = curr_power_of_two curr_power_of_two = curr_power_of_two

Great explanation as always !!! Thank you !

from integers 4 and onwards, why does it not work if we simply just mod it by 2 (n%2) , like we did for 0,1,2,3 ? Before watching this I did it, and the answer is wrong from 4 onwards but I can't figure out why.

you make my life much easier. many thx!

This solution is inspired by your video on simple numbers. Basically we were n&(n-1) to get the 1 and incrementing the counter. here we just do the AND operation then get the amount from dp[n&(n-1)] + 1. for(int i=0;i

Amazing solution! Mine was kinda simpler, but not as elegant as yours. My idea is to access the numbers from 0 to n and, for each number, divide it (using integer division) by 2 until it reaches 0, and while doing this, count the amount of times the remainder of the division was 1. It does not use dp and is, indeed, slower, but it's able to solve in O(n log n) time, since we're iterating n + 1 times for the size of the array, and for each iteration, we're making log_2 (n) division operations :) class Solution { public: vector countBits(int n) { vector ans; int count, aux; for (int i = 0; i 0) { if (aux % 2 == 1) { count++; } aux /= 2; } ans.push_back(count); } return ans; } };

@chloetang211

Жыл бұрын

i have same thought with you but still nor figure out the concrete code yet

@tanmaymathur6833

Жыл бұрын

You can optimize it to O(n); when you divide it by 2, it effectively gives you half for which you can easily store the result int[] ans = new int[n+1]; ans[0] = 0; if (n == 0) { return ans; } ans[1] = 1; if (n == 1) { return ans; } for (int i = 2; i

@arthurc6974

Жыл бұрын

@@tanmaymathur6833 that's actually a great idea. I'm going to study it when I have some time, ty!

Awesome solution!

what if i used the hamming weight function (almost O(1) complexity) to calculate the hamming weights of each bit and add it to the array in one pass??

Idk how this one is considered easy

Thanks for your help

the way this problem is solved out of box and its a bomb thinking,thinktank

I actually solved this one prior to coming and watching this video and somehow I left more confused.

Thanks a lot, sir

Best explanation.

Thank you

Easy explanation. Keep it up. 1000 likes from me.

@NeetCode

3 жыл бұрын

Thanks, much appreciated :)

Mind blowing ❤

awesome vid

9:10 no pun intended

Thank you~

There's no way dp is meant to solve an easy level problem lol. Good explanation nonetheless!

@weaponkid1121

2 жыл бұрын

you're right, the n logn solution works. if dp was needed, it would be a medium question where the n logn solution would exceed the time limit. however dp is needed to solve the follow up question in the problem statement of "can you solve this in n time?"

@dorondavid4698

2 жыл бұрын

@@weaponkid1121 Yeah, exactly

Thats how you write a neat code, haha! Thanks!

@juliuscecilia6005

3 жыл бұрын

That's how you write a neet code** ;)

the best code fun countBits(n: Int): IntArray { val arr = IntArray(n + 1) if (arr.size == 1) return arr arr[1] = 1 for (i in 2 until arr.size) arr[i] = arr[i / 2] + i % 2 return arr }

Thank you.

Hello, Thank you for this great video. I am wondering why in your video for "number of 1 bit", the time complexity for the %2 method is O(1), but in this video, the time complexity for the %2 method is O(nlogn), where the continuous mod 2 contributes to the logn part. Can I argue that the complexity for the %2 approach for this question could also be O(n) as there will only be 32 bits? Thank you very much for answering

@wenqingcao

6 ай бұрын

For "number of 1 bit", the time complexity is O(1) since the problem constraints says: The input must be a binary string of length 32. However, in this problem, we don't have this constrains. Thus I think your statement is correct, " for this question could also be O(n) as there will only be 32 bits ".

I caught that very intentional pun. "lets clean this up a little bit"

9:11 Nice pun ;)

Genius

nice!

used the number of bits solution inside it class Solution: def countBits(self, n: int) -> List[int]: l = list() for i in range (n+1): cnt = 0 k = i while k: k = k & (k-1) cnt += 1 l.append(cnt) return l

this is so crazyy

Do you have any social media handle?

First of all, thank you so much. You are amazing in terms of explanation. But I found there is no pattern to learn from this problem. Have to memorize it.

fking too good

tell me this is Magic, wow bro!

Can anyone tell the brute force approach?

@jayankmayukh4863

2 жыл бұрын

you could just count 1 bits in each integer from 0 to N. If you want to know how to do that you can watch kzread.info/dash/bejne/hK12r5dvgqy9orA.html

@3:24 you meant 0/2 = 0 right?

@marmikpatel8387

11 ай бұрын

1/2 = 0 in programming as we round to infinity.

this question become EASY

Another way to solve this problem is by having a helper function. `def countBits(self, n: int) -> List[int]: ans=[] i=0 while i >1 return res`

@ayushjain1092

Жыл бұрын

This is how I did it, but the time complexity is worse than the dp approach

Your way is the harder way. Just build a table of the first 16 possible numbers (from 0 to 15 inclusive), and just look this up (for example A[15] = 4 (15 in binary contains 4 ones). If the number to count bits is larger than 15 (such as 250), then just treat that as 2 nibbles (a high nibble and a low one). You can easily figure out how many nibbles you will need by for a number x (such as x = 215,000), by taking the ceiling of log base 16 of x. That is the way I would do it. Ceiling(log base 16 of 215,000) = 5. 215,000 in base 2 is 18 digits long, so indeed you would need 5 nibbles.

@trenvert123

Жыл бұрын

Your way sounds more confusing, honestly. I did research nibbles after your explanation though, so thanks. Also, the problem asks that you not use any built in functions to solve it. I'm not sure if log base 16 x would count. Lastly, this problem is to familiarize people with dynamic programming. It's impressive that you know such a cool solution to this problem. But don't you think it'd be easier to just learn dynamic programming?

An alternative: use recursive relation: f(2*n)=f(n), f(2*n+1)=f(n)+1

@randEveScrub

Жыл бұрын

Yea this one seemed way more intuitive to me

How can this be easy?

I don't see how this can be a Easy tagged question.

I'm here because I didn't understand the question 🤦🏼‍♂️

return [i.bit_count() for i in range(n+1)] ;) Hamming weight problem