Code Logo

Counting Bits

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Counting Bits

Solution Approach

DP array of size n+1. For each i, dp[i] = dp[i >> 1] + (i & 1). Return the array.

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

Time O(n), Space 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;
    }
}