Counting Bits - Dynamic Programming - Leetcode 338 - Python
Vložit
- čas přidán 30. 06. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 SPREADSHEET: docs.google.com/spreadsheets/...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/counting...
0:00 - Read the problem
4:28 - Drawing Explanation
11:38 - Coding Explanation
leetcode 338
This question was identified as an amazon interview question from here: github.com/xizhengszhang/Leet...
#counting #bits #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
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.
^
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
Absolutely i was expecting this answer from neetcode any ways its the best python interview preparation channel
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).
Wow. How did you get the idea that (i&1) gives the remaining 1's in binary number?
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))
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;
this is more intuitive than the entire video lol.. thanks for this
THank you for the explanation.
Nice!
genious!
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
Not sure it should be graded as easy problem. Neetcode do really explain every problems in a brilliant way, love it!
Great explanation. First, it seemed very hard to understand. but after watching this video I realized how to solve this problem. thank you.
U a God.. Thanks for explaining the offset swell
[16, 8, 4, 2, 1] - offsets from right to left visually
Thank you for your binary questions update videos!!! Save my life
9:10 Let's clean this up a tiny... bit 😏
Thank you for the amazing explanation!
I'm doing these in java but still find that you have the best explanations... thanks. You truly understand the concepts whereas other CZcamsrs sometimes are just reading solutions
I love your drawing explanation. It's easy to understand. I'd love to know what tool are you using for drawing?
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)
Found your video from leetcode today, Gr8 videos
You are simply the best, your voice is so soothing too :P Thank you buddy, wishing you all the best
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!
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
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;
}
};
i have same thought with you but still nor figure out the concrete code yet
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
@@tanmaymathur6833 that's actually a great idea. I'm going to study it when I have some time, ty!
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
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;
}
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
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??
Awesome solution!
the way this problem is solved out of box and its a bomb thinking,thinktank
Idk how this one is considered easy
I actually solved this one prior to coming and watching this video and somehow I left more confused.
Easy explanation. Keep it up. 1000 likes from me.
Thanks, much appreciated :)
Thanks a lot, sir
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
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 ".
Thanks for your help
Thats how you write a neat code, haha! Thanks!
That's how you write a neet code** ;)
I caught that very intentional pun. "lets clean this up a little bit"
Best explanation.
awesome vid
Thank you
Thank you~
Mind blowing ❤
9:10 no pun intended
There's no way dp is meant to solve an easy level problem lol.
Good explanation nonetheless!
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?"
@@weaponkid1121 Yeah, exactly
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
}
9:11 Nice pun ;)
Thank you.
nice!
Genius
Do you have any social media handle?
this is so crazyy
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
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!
@3:24 you meant 0/2 = 0 right?
1/2 = 0 in programming as we round to infinity.
Can anyone tell the brute force approach?
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 czcams.com/video/RyBM56RIWrM/video.html
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.
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?
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`
This is how I did it, but the time complexity is worse than the dp approach
How can this be easy?
An alternative: use recursive relation: f(2*n)=f(n), f(2*n+1)=f(n)+1
Yea this one seemed way more intuitive to me
this question become 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