Counting Bits

Back to problems

Leetcode

Medium

Arrays

Bit Manipulation

Dynamic Programming

Counting Bits

Return an array where each position stores the number of set bits in the binary representation of its index.

Acceptance 100%

Start Practice

Problem Statement

Given a non-negative integer n, compute an array ans of length n + 1 such that for every i in the range 0 <= i <= n, ans[i] is the number of 1 bits in the binary representation of i.

Your goal is to fill the array efficiently, rather than counting bits from scratch for every number.

Input Format

A single integer n.

Output Format

Return an integer array ans of size n + 1.
ans[i] should equal the popcount of i for each 0 <= i <= n.

Constraints

0 <= n
The answer must include all values from 0 through n.

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 5

Output

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

Explanation

0 -> 0 bits 1 -> 1 bit 2 -> 1 bit 3 -> 2 bits 4 -> 1 bit 5 -> 2 bits

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress