Counting Bits
Problem Statement
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.
Constraints:
- 0 <= n <= 10^5
Input Format:
- An integer n
Output Format:
- Return an array of length n + 1 such that ans[i] is the number of 1's in the binary representation of i.
Examples:
Example 1:
Input:
n = 2
Output:
[0,1,1]
Explanation:
0 --> 0 (0 ones), 1 --> 1 (1 one), 2 --> 10 (1 one)
Example 2:
Input:
n = 5
Output:
[0,1,1,2,1,2]
Explanation:
0 --> 0 (0 ones), 1 --> 1 (1 one), 2 --> 10 (1 one), 3 --> 11 (2 ones), 4 --> 100 (1 one), 5 --> 101 (2 ones)
Solutions
Dynamic Programming Approach
Use the observation that the number of 1's in i equals the number of 1's in i/2 plus 1 if i is odd.
Last Set Bit Approach
Use the observation that the number of 1's in i equals the number of 1's in (i & (i-1)) plus 1. This is because (i & (i-1)) clears the rightmost set bit in i.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Initialize ans = [0, 0, 0, 0, 0, 0] (array of length n+1)
- Process i=1: Binary is 1. ans[1] = ans[0] + 1 = 0 + 1 = 1. ans = [0, 1, 0, 0, 0, 0]
- Process i=2: Binary is 10. ans[2] = ans[1] + 0 = 1 + 0 = 1. ans = [0, 1, 1, 0, 0, 0]
- Process i=3: Binary is 11. ans[3] = ans[1] + 1 = 1 + 1 = 2. ans = [0, 1, 1, 2, 0, 0]
- Process i=4: Binary is 100. ans[4] = ans[2] + 0 = 1 + 0 = 1. ans = [0, 1, 1, 2, 1, 0]
- Process i=5: Binary is 101. ans[5] = ans[2] + 1 = 1 + 1 = 2. ans = [0, 1, 1, 2, 1, 2]
- Return ans = [0, 1, 1, 2, 1, 2]
Hints
Hint 1
Hint 2
Hint 3
Hint 4
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize how the array is built up step by step, showing the binary representation of each number and how the bits are calculated.
Key visualization elements:
- current number
- binary representation
- current calculation
Similar Questions
Number of 1 Bits
EasyWrite a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
Reverse Bits
EasyReverse bits of a given 32 bits unsigned integer. Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
Implementation Notes
This problem combines dynamic programming with bit manipulation concepts. It's a good demonstration of how we can use patterns in binary representations to optimize solutions.