89. Counting Bits · DSA Practice

Return an array ans of length n + 1 where ans[i] is the number of 1 bits in i. Try for O(n).

Example 1

Input: n = 2

Output: [0,1,1]

Example 2

Input: n = 5

Output: [0,1,1,2,1,2]

Hint 1

i >> 1 drops the last bit, and you already know its answer.

Bit ManipulationDynamic Programming

Approach 1: Popcount each

Count bits of every number.

⏱ Time O(n log n)💾 Space O(1)

Approach 2: DP on bits ✅

ans[i] = ans[i >> 1] + (i & 1).

⏱ Time O(n)💾 Space O(1) extra

Reference solution for DP on bits (time O(n), space O(1) extra). Each solution passes every test in all four languages.

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)   # bits of i = bits of i/2, plus the last bit
        return ans

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

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1, 0);
        for (int i = 1; i <= n; i++) ans[i] = ans[i >> 1] + (i & 1);
        return ans;
    }
};

function countBits(n) {
  const ans = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) ans[i] = ans[i >> 1] + (i & 1);
  return ans;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

This problem is explained in the lesson Bit Manipulation.