Coding Interview PatternsCounting Bits
EasyBitwise Manipulation

Counting Bits

Explanation & Solution

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

Input: n = 2

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

Explanation:

  • 0 --> 0
  • 1 --> 1
  • 2 --> 10

Constraints

  • 0 <= n <= 10^5

Follow up: Write a solution in linear time O(n) and use only O(n) extra space.

Approach

Bitwise Manipulation pattern

Key Insight

  • Each number shares all bits with its right-shifted version except the last bit
  • This allows us to build the answer for larger numbers from smaller ones in a single pass
  • Time: O(n) | Space: O(n)

Solution Code

Previous
Number of 1 Bits
Next
Reverse Bits