Back to DSA

Counting Bits

easy
Acceptance: 65%
Bit ManipulationDynamic Programming

Given a non-negative integer n, produce an array of length n + 1 in which the value at index i equals the number of 1-bits in the binary representation of i.

Examples

Example 1:
Input:n = 3
Output:[0,1,1,2]
Example 2:
Input:n = 7
Output:[0,1,1,2,1,2,2,3]

Hints

Related Problems

House RobbermediumClimbing StairseasyLongest Increasing SubsequencemediumWord BreakmediumEdit Distancehard
00:00
class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) dp[i] = dp[i >> 1] + (i & 1);
        return dp;
    }
}
Time complexityO(n)
Space complexityO(n)