Counting Bits - Dynamic Programming - Leetcode 338 - Python

0:00 - Read the problem
4:28 - Drawing Explanation
11:38 - Coding Explanation

leetcode 338

#counting #bits #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[marmikpatel]

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.

[Grimreap]

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

[michaelchen]

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

[莊凱翔-eh]

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

[nikkis]

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

[mingyan]

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;

[tamashada]

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]

9:10 Let's clean this up a tiny... bit 😏

Thank you for the amazing explanation!

[samandarboymurodov]

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

[jackedelic]

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)

[edwardteach]

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

[bit_hero]

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

for(int i=1;i<n+1;i++){
v[i]=v[i>>1]+(i&1);
}
return v;
}

[arthurc]

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<int> countBits(int n) {
vector<int> ans;
int count, aux;
for (int i = 0; i <= n; i++) {
count = 0;
aux = i;
while (aux > 0) {
if (aux % 2 == 1) {
count++;
}
aux /= 2;
}
ans.push_back(count);
}
return ans;
}
};

[shuoj.]

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

[nikhilgumidelli]

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

[squid]

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 << 1
dp[i] = 1 + dp[i - previous_power_of_two]
return dp

Table of 2's below:

0 = 0000 2^0
1 = 0001

2 = 0010 2^1
3 = 0011

4 = 0100 2^2
5 = 0101
6 = 0110
7 = 0111

8 = 1000 2^3 = 8, right here we would do 1 + [0-8]
9 = 1001
10 = 1010
11 = 1011
12 = 1100
13 = 1101
14 = 1110
15 = 1111

16 = 10000 2^4

1 + [0-16] 2^16 = 32

[nihalbhandary]

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<n;i++){
int j = i&(i+1);
res[i+1]=res[j]+1;
}

[tuhoctiengtrunghichinese]

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

[ks-mqfm]

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

[mujahirabbasi]

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