Counting Bits: the idea to remember.

The core insight

The count for i equals the count for i shifted right plus its last bit.

Why it works

Shifting drops exactly the least significant bit. The remaining smaller number has already been solved.

The mistake to avoid

Include index zero and allocate n plus one output slots.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

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

Make the next connection