Counting Bits - Practice Coding Problems

Counting Bits - Problem

Given an integer n, return an array ans of length n + 1 such that for each i (where 0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

For example, if n = 2, the array should contain the count of 1-bits for numbers 0, 1, and 2:

0 in binary is 0 → 0 ones
1 in binary is 1 → 1 one
2 in binary is 10 → 1 one

So the result would be [0, 1, 1].

Input & Output

Example 1 — Basic Case

$ Input: n = 2

› Output: [0,1,1]

💡 Note: 0 in binary: 0 → 0 ones, 1 in binary: 1 → 1 one, 2 in binary: 10 → 1 one. Result: [0,1,1]

Example 2 — Larger Range

$ Input: n = 5

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

💡 Note: Count 1-bits: 0→0, 1→1, 2(10)→1, 3(11)→2, 4(100)→1, 5(101)→2

Example 3 — Single Number

$ Input: n = 0

› Output: [0]

💡 Note: Only need to count bits for 0, which has zero 1-bits

Constraints

0 ≤ n ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Given n, we need counts for 0, 1, 2, ..., n

Process

Count 1-bits in binary representation of each number

Output

Array where ans[i] = count of 1-bits in i

Key Takeaway

🎯 Key Insight: Use dynamic programming to build each result from previously computed smaller numbers

Asked in

Apple 25 M Microsoft 20 G Google 15

The key insight is recognizing that each number's 1-bit count can be derived from a previously computed smaller number. The optimal Dynamic Programming approach uses either dp[i] = dp[i >> 1] + (i & 1) or dp[i] = dp[i & (i-1)] + 1. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - Build from Previous Results	O(n)	O(1)	Use the insight that dp[i] = dp[i >> 1] + (i & 1) to build results incrementally
Bit Manipulation - Remove Rightmost 1-bit	O(n)	O(1)	Use the property that dp[i] = dp[i & (i-1)] + 1, where i & (i-1) removes the rightmost 1-bit
Brute Force - Count Bits for Each Number	O(n log n)	O(1)	For each number from 0 to n, count the 1-bits by checking each bit position

Dynamic Programming - Build from Previous Results — Algorithm Steps

Initialize dp array with dp[0] = 0
For each i from 1 to n, use dp[i] = dp[i >> 1] + (i & 1)
Right shift i by 1 gives us i/2, which we already computed
Add 1 if the least significant bit of i is 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Base Case

dp[0] = 0 (zero has no 1-bits)

Recurrence

dp[i] = dp[i>>1] + (i&1)

Build Up

Each result uses a previously computed value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int* solution(int n, int* returnSize) {
    *returnSize = n + 1;
    int* dp = (int*)calloc(*returnSize, sizeof(int));
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}

int main() {
    int n;
    scanf("%d", &n);
    int returnSize;
    int* result = solution(n, &returnSize);
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop through numbers 0 to n, each computation is O(1)

✓ Linear Growth

Space Complexity

O(1)

Only using the output array, no additional data structures

✓ Linear Space

523.0K Views

High Frequency

~15 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - Build from Previous Results — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler