Counting Bits easy

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.

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

Steps and Explanation

The most straightforward approach involves iterating through each number from 0 to n, converting it to its binary representation, and counting the number of 1s. However, this approach can be inefficient for larger values of n. A more efficient approach leverages the following observation:

The number of 1s in the binary representation of a number i is related to the number of 1s in the binary representation of i/2 (integer division). Specifically:

• If i is even, the number of 1s in i is the same as the number of 1s in i/2.
• If i is odd, the number of 1s in i is one more than the number of 1s in i/2.

We can use dynamic programming to efficiently compute the number of 1s for each number. We create an array dp where dp[i] stores the number of 1s in the binary representation of i. We initialize dp[0] = 0. Then, for each i from 1 to n, we compute dp[i] based on the value of dp[i/2] according to the rules above.

Code

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n + 1);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            if (i % 2 == 0) {
                dp[i] = dp[i / 2];
            } else {
                dp[i] = dp[i / 2] + 1;
            }
        }
        return dp;
    }
};

Complexity Analysis

• Time Complexity: O(n). We iterate through the numbers from 0 to n once.
• Space Complexity: O(n). We use an array dp of size n+1 to store the results. This is unavoidable since we need to return an array of size n+1.