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.
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
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).
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))
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;
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
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:)
I'm doing these in java but still find that you have the best explanations... thanks. You truly understand the concepts whereas other RUclipsrs sometimes are just reading solutions
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)
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; } };
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
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
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
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
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
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 ```
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 }
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.
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 ".
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
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?"
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?
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.
I've managed to solve this one with O(1) space and O(n) time class Solution { private var lastNumber = 0 private var lastValue = 0 fun countBits(n: Int): IntArray { var result = IntArray(n+1) for(num in 0 .. n) { result[num] = countOnes(num) } return result } private fun countOnes(n: Int): Int { var result = 0 var num = n while(num > 0) { num = num and (num-1) if(lastNumber == num) { result = 1 + lastValue num = 0 } else { result++ } } lastValue = result lastNumber = n return result } }
![Felix "Unfair" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/Oswujxm2Ag0/mqdefault.jpg)
![Noob To Max With DRAGON REWORK In Blox Fruits [FULL MOVIE]](http://i.ytimg.com/vi/LnBMOinoOvA/mqdefault.jpg)
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.
absolutely
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!
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:)
I'm doing these in java but still find that you have the best explanations... thanks. You truly understand the concepts whereas other RUclipsrs sometimes are just reading solutions
9:10 Let's clean this up a tiny... bit 😏
Thank you for the amazing explanation!
Great explanation. First, it seemed very hard to understand. but after watching this video I realized how to solve this problem. thank you.
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)
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;
}
};
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!
U a God.. Thanks for explaining the offset swell
[16, 8, 4, 2, 1] - offsets from right to left visually
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
Thank you for your binary questions update videos!!! Save my life
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
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
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
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
```
the way this problem is solved out of box and its a bomb thinking,thinktank
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??
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
}
I love your drawing explanation. It's easy to understand. I'd love to know what tool are you using for drawing?
we can use fenwick tree idea here to off the last right most bit.
formula = ans[i] = ans[i - (i & -i)] + 1
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 are simply the best, your voice is so soothing too :P Thank you buddy, wishing you all the best
I actually solved this one prior to coming and watching this video and somehow I left more confused.
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 ".
Easy explanation. Keep it up. 1000 likes from me.
Thanks, much appreciated :)
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
Found your video from leetcode today, Gr8 videos
Awesome solution!
I caught that very intentional pun. "lets clean this up a little bit"
Idk how this one is considered easy
It's actually a pretty easy question
Great explanation as always !!! Thank you !
fantastic explanation
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
you make my life much easier. many thx!
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
9:11 Nice pun ;)
Thats how you write a neat code, haha! Thanks!
That's how you write a neet code** ;)
@3:24 you meant 0/2 = 0 right?
1/2 = 0 in programming as we round to infinity.
Mind blowing ❤
Best explanation.
Do you have any social media handle?
That not how programmers count bits, at least not efficiently, dynamic programming is not a golden hammer
Thanks for your help
Thank you.
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
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?
Thanks a lot, sir
Thank you
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.
I've managed to solve this one with O(1) space and O(n) time
class Solution {
private var lastNumber = 0
private var lastValue = 0
fun countBits(n: Int): IntArray {
var result = IntArray(n+1)
for(num in 0 .. n) {
result[num] = countOnes(num)
}
return result
}
private fun countOnes(n: Int): Int {
var result = 0
var num = n
while(num > 0) {
num = num and (num-1)
if(lastNumber == num) {
result = 1 + lastValue
num = 0
} else {
result++
}
}
lastValue = result
lastNumber = n
return result
}
}
Thank you~
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 ruclips.net/video/RyBM56RIWrM/видео.html
awesome vid
awesome!!
funny how explanations can look long and tedious but when writing the code, it takes 1 minute, if that .
How can this be easy?
tell me this is Magic, wow bro!
Genius
I don't see how this can be a Easy tagged question.
nice!
this question become EASY
I'm here because I didn't understand the question 🤦🏼♂️
Not a clue what this does 😆
v[0]=0;
v[1]=1;
for(int i=2;i
return [i.bit_count() for i in range(n+1)] ;) Hamming weight problem