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 set bits (1s). However, this approach can be inefficient for larger values of n. A more efficient approach utilizes the following observation:

The number of 1s in the binary representation of a number x can be obtained by adding 1 to the number of 1s in the binary representation of x/2 (integer division) if x is even, otherwise it's the same as the number of 1s in x/2. This is because when we divide by 2 (right bit shift), we effectively remove the least significant bit. If the least significant bit was 0 (even number), the number of 1s remains the same. If it was 1 (odd number), the number of 1s decreases by 1.

This recursive relationship allows us to build the solution iteratively and efficiently. We can create a dp (dynamic programming) array to store the results, where dp[i] will store the number of 1s in the binary representation of i.

Code (Java)

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0; // Base case: 0 has 0 set bits

        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0) { // Even number
                dp[i] = dp[i / 2]; 
            } else { // Odd number
                dp[i] = dp[i / 2] + 1;
            }
        }
        return dp;
    }
}

Complexity Analysis

• Time Complexity: O(n). We iterate through the numbers from 1 to n once. Each operation inside the loop (division, modulo, and array access) takes constant time.
• Space Complexity: O(n). We use an array dp of size n+1 to store the results.

This optimized approach significantly reduces the time complexity compared to the naive approach which would involve converting each number to binary, requiring O(n log n) time. The space complexity is linear due to storing the results in the dp array.