#0247

Counting Bits

EasyDSA18 min10 XP

Problem

Given n, return a list ans where ans[i] is the number of set bits in the binary representation of i.

Why This Matters

Counting bits introduces bit DP: reuse the answer for a smaller number instead of recounting from scratch.

Function Signature

def count_bits(n):

Examples

Example 1

Inputn = 5

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

0, 1, 10, 11, 100, 101 have bit counts 0, 1, 1, 2, 1, 2.

Constraints

Return the exact requested value.
Handle empty or small inputs when the prompt allows them.
Prefer the target DSA pattern over brute force when the input can grow.

CodePython

def count_bits(n):
    """
    Input example: n = 5
    Return: [0, 1, 1, 2, 1, 2]
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return []

def count_bits(n):
    """
    Input example: n = 5
    Return: [0, 1, 1, 2, 1, 2]
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return []

Visible browser tests run here when available.

Testcases2 visible / 3 hidden categories

Up to five

Input5

Expected[0, 1, 1, 2, 1, 2]

Each answer reuses i // 2 and the last bit.

Zero only

Input0

Expected[0]

Only 0 is included.

Hidden Test Categories

larger npower of two boundaryodd and even mix