Code Logo

Counting Bits

Published at24 Jul 2026
Created by
Easy 1 views
Like0

Given an integer n, return an array ans of length n+1 where ans[i] is the number of 1 bits in the binary representation of i. The solution should run in O(n) time, not O(n * bits) by counting bits individually.

The key DP insight is that removing the least significant bit from i gives i >> 1 (integer division by 2), which is a smaller number whose bit count is already computed. If i is even, the LSB is 0, so bits are the same as i >> 1. If i is odd, the LSB is 1, so bits are one more than i >> 1. This gives:dp[i] = dp[i >> 1] + (i & 1).

This recurrence works because the binary representation of i is the binary representation of i >> 1 shifted left by one, with the LSB appended. The number of 1 bits in i is therefore the number in i >> 1 plus whether the LSB is 1. This uses previously computed values to build the solution incrementally.

Edge cases include n = 0 (return [0]), n = 1 (return [0,1]), and large n up to 10^5 where the O(n) algorithm handles efficiently.

The bit counting DP is a classic example of using binary representation properties to derive a recurrence. The relation dp[i] = dp[i >> 1] + (i & 1) works because shifting right removes the LSB, and the discarded bit contributes 1 if it was set.

Example Input & Output

Example 1
Input
0
Output
[0]
Explanation

Only 0.

Example 2
Input
1
Output
[0,1]
Explanation

0 and 1.

Example 3
Input
2
Output
[0,1,1]
Explanation

0:0, 1:1, 2:10 → [0,1,1]

Example 4
Input
3
Output
[0,1,1,2]
Explanation

0 through 3.

Example 5
Input
5
Output
[0,1,1,2,1,2]
Explanation

3:11, 4:100, 5:101 → [0,1,1,2,1,2]

Algorithm Flow

Recommendation Algorithm Flow for Counting Bits

Solution Approach

For each number from 0 to n, count the number of 1 bits in its binary representation. Use dynamic programming with the pattern that the number of 1 bits in i equals the count for i >> 1 (i divided by 2, which is i without the last bit) plus the last bit (i & 1). This gives dp[i] = dp[i >> 1] + (i & 1).

function countBits(n) {
  var dp = Array(n + 1).fill(0);
  for (var i = 1; i <= n; i++) {
    dp[i] = dp[i >> 1] + (i & 1);
  }
  return dp;
}

For example, the binary of 5 is 101. 5 >> 1 is 2 (binary 10) which has 1 one-bit, and 5 & 1 is 1. So dp[5] = dp[2] + 1 = 1 + 1 = 2. This recurrence uses previously computed values to avoid redundant bit-counting.

Time complexity is O(n), space complexity is O(n).

Best Answers

java
class Solution {
    public int[] solution(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
}