Counting Bits Problem

Counting Bits Problem — ExecCode Easy DSA Practice

Solve the Counting Bits problem on ExecCode. Free online easy DSA practice in Bit Manipulation. Write and run code in Java, C++, Python — no signup required to run.

Problem description

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 1s in the binary representation of i.

Examples

Input n = 2; Output [0, 1, 1]. Input n = 5; Output [0, 1, 1, 2, 1, 2]. Input n = 0; Output [0]

Constraints

0 <= n <= 100000 Answer must run in O(n) time

Practice Counting Bits free on ExecCode. Browse DSA problems, topic map, and placement guides.