This practice workspace is built for desktop. Open it on a larger screen to start solving.

Counting Bits

Dynamic Programming·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.

The classic O(n) DP recurrence is ans[i] = ans[i >> 1] + (i & 1).

Examples

Input: n = 2

Output: [0,1,1]

0 -> 0b0 (0 ones), 1 -> 0b1 (1 one), 2 -> 0b10 (1 one).

Input: n = 5

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

Counts of 1-bits for 0..5.

Constraints

0 <= n <= 10^5

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Dynamic Programming
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.