Counting Bits

Asked byAmazonGoogleBloombergJPMorgan

Problem

Given an integer n, return an array of length n+1 where the value at index i is the number of '1' bits in the binary representation of i.

Examples

Example 1

Input:n = 2

Output:[0,1,1]

Example 2

Input:n = 5

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

Constraints

0 <= n <= 10^5

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Bit Manipulation pattern

Work directly on a number's binary representation using bitwise operators — often turning an O(n) or O(log n) problem into a handful of O(1) operations.

Look for this pattern when

The problem talks about bits directly (count set bits, reverse bits, single number among duplicates).
You want a constant-time trick instead of a loop for a numeric problem.

Read the full Bit Manipulation guide →

Video walkthroughs

Original problem on LeetCode ↗