Counting Bits - Dynamic Programming - Leetcode 338

Counting Bits - Dynamic Programming - Leetcode 338 - Python

Рет қаралды 140,774

Күн бұрын

Пікірлер: 99

@marmikpatel8387 Жыл бұрын

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.

@mclwizlon 4 ай бұрын

absolutely

@Grimreap191 3 жыл бұрын

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

@juliuscecilia6005 3 жыл бұрын

@michaelchen9275 3 жыл бұрын

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 3 жыл бұрын

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))

@AlgoStuffYT 2 жыл бұрын

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

@nikkis8102 8 ай бұрын

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

@莊凱翔-e1h 6 ай бұрын

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

@mingyan8081 2 жыл бұрын

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 Жыл бұрын

genious!

@SharmaTushar1-yt Жыл бұрын

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

@tamashada8006 22 күн бұрын

I do not know if anyone posted before but my idea was based on the fact that the pattern is exponentially repeats itself just by adding 1 to the elements of the previous section (which in total sums up to a one pass iteration): 0, 0+1 -> 0, 1 0, 1, 0+1, 1+1 -> 0, 1, 1, 2 0, 1, 1, 2, 0+1, 1+1, 1+1, 2+1 -> 0, 1, 1, 2, 1, 2, 2, 3 and the algorithm: class Solution: def countBits(self, n: int) -> List[int]: ans = [0] if not n: return ans while True: for i in range(len(ans)): ans.append(ans[i]+1) if len(ans) == n+1: return ans Anyways a lot of appreciation for the work for Neetcode and the community around it:)

@JonathanBatchelder 3 жыл бұрын

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

@jackedelic9188 Жыл бұрын

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)

@arthurc6974 2 жыл бұрын

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; } };

@tanmaymathur6833 2 жыл бұрын

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 2 жыл бұрын

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

@samandarboymurodov8941 3 жыл бұрын

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

@8bit_hero850 2 жыл бұрын

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; }

@mujahirabbasi6270 Ай бұрын

My solution : class Solution(object): def countBits(self, n): """ :type n: int :rtype: List[int] """ output = [0] * (n + 1) # recurrence relation for i in range(1, n + 1): output[i] = output[i >> 1] + (i & 1) return output you can read the recurrence relation as : the number of 1's in i = the number of 1's in i>>1 + the last bit (least significant bit which will be zero for even numbers and one for odd numbers) in i

@nikhilgumidelli6308 2 жыл бұрын

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

@nihalbhandary162 Жыл бұрын

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

@edwardteach2 3 жыл бұрын

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

@squid84202 6 ай бұрын

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

@shuoj.2038 3 жыл бұрын

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

@asdkjfhaklhzvkl 6 ай бұрын

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 ```

@ks-mq3fm 3 жыл бұрын

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

@brm266 Жыл бұрын

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 }

@amol_ 3 ай бұрын

we can use fenwick tree idea here to off the last right most bit. formula = ans[i] = ans[i - (i & -i)] + 1

@MaxFung 9 ай бұрын

Idk how this one is considered easy

@Anonymous-fr2op 3 ай бұрын

It's actually a pretty easy question

@tanim913 2 жыл бұрын

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

@dayanandraut5660 3 жыл бұрын

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

@NeetCode 3 жыл бұрын

Thanks, much appreciated :)

@mapledanish3662 Жыл бұрын

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

@tuhoctiengtrunghichinese 2 жыл бұрын

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

@dorondavid4698 3 жыл бұрын

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

@ShivangiSingh-wc3gk 2 жыл бұрын

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

@aaronhansonofficial 2 жыл бұрын

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

@Thenammaithenu Жыл бұрын

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

@bujagawnisaitejagoud2461 Жыл бұрын

Awesome solution!

@prabinlamsal74 Жыл бұрын

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??

@KexinHao Жыл бұрын

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 10 ай бұрын

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 ".

@rahulshetty9335 3 жыл бұрын

Found your video from leetcode today, Gr8 videos

@MP-ny3ep Жыл бұрын

Great explanation as always !!! Thank you !

@noumaaaan 2 жыл бұрын

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.

@mclwizlon 4 ай бұрын

fantastic explanation

@gagemachado2597 Жыл бұрын

9:10 no pun intended

@hoyinli7462 3 жыл бұрын

you make my life much easier. many thx!

@ygwg6145 Жыл бұрын

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

@amadousallah8916 Жыл бұрын

Thank you.

@nileshdhamanekar4545 3 жыл бұрын

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

@juliuscecilia6005 3 жыл бұрын

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

@SRoyGardening 2 жыл бұрын

Best explanation.

@davidjames1684 2 жыл бұрын

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?

@maimousa576 6 ай бұрын

Thanks for your help

@socify4410 Жыл бұрын

Mind blowing ❤

@pavanreddy1568 2 жыл бұрын

Thank you

@michaelyao9389 2 жыл бұрын

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.