338.md

LeetCode #338: Counting Bits

🔗 Problem Link: Counting Bits

Problem Statement 🟢 Difficulty: Easy

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example 1

Input: n = 2  
Output: [0,1,1]  
Explanation:  
0 -> 0 (0 ones)  
1 -> 1 (1 one)  
2 -> 10 (1 one)

Example 2

Copy
Edit
Input: n = 5  
Output: [0,1,1,2,1,2]  
Explanation:  
0 -> 0   (0 ones)  
1 -> 1   (1 one)  
2 -> 10  (1 one)  
3 -> 11  (2 ones)  
4 -> 100 (1 one)  
5 -> 101 (2 ones)  

Constraints

0 <= n <= 10^5

Approach 1: Dynamic Programming (Most Significant Bit)

We can use previously computed values instead of recalculating the number of 1’s from scratch.

Key observation:

A number i has the same number of 1’s as i - 2^m, where 2^m is the largest power of 2 ≤ i.
Example:
5 (101) = 1 + (1 of 1)
6 (110) = 1 + (1 of 2)

Formula:

countBits ( 𝑖 )

1 + countBits ( 𝑖 − largest power of 2 ) countBits(i)=1+countBits(i−largest power of 2)