Counting Bits

EASY

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

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

0 <= n <= 10⁵

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Approaches

Checkout 3 different approaches to solve Counting Bits. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Iterate and Count Bits

This is a straightforward brute-force approach. We iterate through each number from 0 to n. For each number, we manually count the number of set bits (1s) in its binary representation by repeatedly checking the last bit and shifting.

Algorithm

Initialize an array ans of size n + 1.
Loop i from 0 to n:
- Initialize count = 0 and num = i.
- While num > 0:
  - Add the last bit to the count: count += num & 1.
  - Right shift the number to process the next bit: num >>= 1.
- Store the result: ans[i] = count.
Return ans.

The algorithm iterates through each integer from 0 to n. For each integer i, it calculates the number of set bits. This is done using a nested loop where we check the least significant bit (LSB) of the current number. If the LSB is 1, we increment a counter. Then, we perform a right bit shift on the number to discard the LSB and check the next bit. This process is repeated until the number becomes 0. The final count for i is stored in ans[i].

public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int count = 0;
        int num = i;
        while (num > 0) {
            count += num & 1;
            num >>= 1;
        }
        ans[i] = count;
    }
    return ans;
}

Complexity Analysis

Time Complexity: O(n log n) - The outer loop runs `n + 1` times. For each number `i`, the inner while loop runs `log(i)` times (the number of bits in `i`). Therefore, the total time complexity is the sum of `log(i)` for `i` from 1 to `n`.Space Complexity: O(n) - The space required is for the output array `ans` of size `n + 1`. If the output array is not considered, the space complexity is O(1).

Pros and Cons

Pros:

Simple to understand and implement.
Does not require any complex mathematical insights.

Cons:

Inefficient compared to linear time solutions.
It recomputes the bit count for each number from scratch, ignoring relationships between numbers.

Code Solutions

Checking out 3 solutions in different languages for Counting Bits. Click on different languages to view the code.

class Solution {
public
  int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 1; i <= n; ++i) {
      ans[i] = ans[i & (i - 1)] + 1;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Counting Bits

Patterns:

Dynamic ProgrammingBit Manipulation

Companies:

Nvidia |