grid47 Exploring patterns and algorithms
Oct 4, 2024
4 min read
Solution to LeetCode 338: Counting Bits Problem
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.
Problem
Approach
Steps
Complexity
Input: You are given an integer n.
Example: n = 3
Constraints:
• 0 <= n <= 10^5
Output: Return an array ans such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Example: [0, 1, 1, 2]
Constraints:
• The solution must run in linear time O(n).
Goal: Calculate the number of 1's in the binary representation for each number from 0 to n.
Steps:
• Initialize an array res of size n + 1 with 0s.
• For each number i from 0 to n, set res[i] = res[i >> 1] + (i & 1).
• Return the array res.
Goal: The solution must be efficient with O(n) time complexity and without using any built-in popcount functions.
Steps:
• The solution must run efficiently for n values as large as 10^5.
Assumptions:
• The value of n is within the given constraints.
• Input: n = 3
• Explanation: For the input n = 3, the binary representations of 0, 1, 2, and 3 are '0', '1', '10', '11'. The number of 1's in these binary numbers are 0, 1, 1, and 2 respectively.
• Input: n = 6
• Explanation: For the input n = 6, the binary representations of 0, 1, 2, 3, 4, 5, and 6 are '0', '1', '10', '11', '100', '101', '110'. The number of 1's in these binary numbers are 0, 1, 1, 2, 1, 2, and 2 respectively.
Approach: To solve this problem, we can calculate the number of 1's in the binary representation of each integer from 0 to n using an efficient approach.
Observations:
• We need to avoid using built-in functions like popcount to solve the problem.
• We can use bitwise operations to compute the number of 1's in a number's binary representation.
Steps:
• Create an array res of size n + 1 initialized to 0.
• Iterate over each number i from 0 to n, updating res[i] as res[i >> 1] + (i & 1).
• Return the array res.
Empty Inputs:
• If n = 0, the output should be [0].
Large Inputs:
• For large values of n (up to 10^5), ensure the solution runs in linear time.
Special Values:
• Consider cases where all the numbers in the range have the same number of 1's in their binary representation, such as n = 0.
Constraints:
• The solution should not exceed O(n) time complexity.
vector<int> countBits(int n) {
vector<int> res(n +1, 0);
for(int i =0; i <= n; i++) {
res[i] = res[i >>1] + (i &1);
}
return res;
}
1 : Function Declaration
vector<int> countBits(int n) {
This is the declaration of the `countBits` function, which takes an integer `n` and returns a vector of integers representing the number of set bits (1's) in the binary representation of each integer from 0 to `n`.
2 : Vector Initialization
vector<int> res(n +1, 0);
A vector `res` is initialized with `n + 1` elements, all set to 0. This will store the number of set bits for each integer from 0 to `n`.
3 : For Loop Setup
for(int i =0; i <= n; i++) {
A `for` loop is used to iterate over all integers from 0 to `n`. In each iteration, the number of set bits in `i` will be calculated.
4 : Bit Calculation
res[i] = res[i >>1] + (i &1);
For each integer `i`, the number of set bits is calculated by shifting `i` right by 1 (`i >> 1`) and adding the least significant bit (`i & 1`). This approach uses dynamic programming to build the solution efficiently.
5 : Return Statement
return res;
After the loop completes, the vector `res` containing the count of set bits for all integers from 0 to `n` is returned.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear because we only iterate over the numbers from 0 to n once.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we store the result in an array of size n + 1.
