Medium · Bit DP
Understand → Visualise → Practice.
Right-shifting x removes its least-significant bit. Therefore the number of set bits in x equals the count for x >> 1 plus x & 1.
dp[x] = dp[x >> 1] + (x & 1), and x >> 1 is always smaller than x.
dp[0] = 0.
Reuse dp[x >> 1].
x & 1 is 0 for even and 1 for odd.
O(n) time and O(n) output space.
Converting every number to a binary string adds avoidable work.
Read the full guide first: Bit Manipulation and Bitmask Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.