For every number i from 0 to n, count the 1 bits in i. Return all the counts in an array.
DSA Animator › DSA Revision › Bit Manipulation › Counting Bits
Remember: i shifted right is i without its last bit. Dynamic programming over smaller numbers. The video solves Counting Bits (LeetCode 338, Easy) with the DP on Bits pattern from the Bit Manipulation topic, and you can replay every step in the interactive Counting Bits animation.
For every number i from 0 to n, count the 1 bits in i. Return all the counts in an array.
For n equal to 5, the answer is 0, 1, 1, 2, 1, 2.
Counting the bits of each number separately takes O of n log n. But each count can be built from a smaller number.
Shifting i right by one drops its last bit. So i has the same bits as i shifted right, plus its last bit. That gives the rule: bits of i equals bits of i over 2, plus i AND 1. Because i over 2 is smaller, its count is already in the array.
bits of 0 is 0. 1 is 1 shifted, which is 0, plus last bit 1, so 1. 2 is 10: half is 1 with count 1, plus last bit 0, so 1. 3 is 11: half is 1, plus last bit 1, so 2. 4 is 100: half is 2 with count 1, so 1. 5 is 101: half is 2, plus 1, so 2.
In code, create an array of size n plus 1. For i from 1 to n, set ans of i to ans of i shifted right by one, plus i AND 1. Return the array, so it's O of n time.
Remember: i shifted right is i without its last bit. Dynamic programming over smaller numbers.