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.

Examples

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

Solution

Method 1 - Naive

Here is the naive approach:

1. Loop through all integers from 0 to n.
2. For each integer, count the number of 1’s in its binary representation using repeated division by 2 (to extract each bit).
3. Store the count for the integer in the result array.

Code

Java

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            ans[i] = countOnes(i);
        }

        return ans;
    }

    private int countOnes(int x) {
        int count = 0;

        while (x != 0) {
            if (x % 2 == 1) {
                count++;
            }
            x /= 2; // Move to the next bit
        }

        return count;
    }
}

Python

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans: List[int] = [0] * (n + 1)
        
        for i in range(n + 1):
            ans[i] = self._count_ones(i)

        return ans

    def _count_ones(self, x: int) -> int:
        count: int = 0
        
        while x != 0:
            if x % 2 == 1:
                count += 1
            x //= 2  # Move to the next bit
        
        return count

Complexity

• ⏰ Time complexity: O(n log n), log N time to find countOnes as we divide number logN times and we have to do it for n numbers.
• 🧺 Space complexity: O(1)

Method 2 - Follow the pattern

Numbers like 2 (10 in binary), 4 (100 in binary), 8 (1000 in binary), 16 (10000 in binary), and so on — which are powers of 2 — have exactly one set bit (1) in their binary representation. For any other number, it can be expressed as 2^m + x, where x is a smaller number. For example, 9 can be written as 8 + 1, and 10 as 8 + 2. The number of set bits for such numbers is equal to 1 (from 2^m) plus the count of set bits in x, which has already been computed.

This insight helps us efficiently count the set bits for numbers by leveraging previously computed results, reducing redundant calculations.

For number 2(10), 4(100), 8(1000), 16(10000), …, the number of 1’s is 1. Any other number can be converted to be 2^m + x. For example, 9=8+1, 10=8+2. The number of 1’s for any other number is 1 + # of 1's in x .

Code

Java

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];  // Result array to store counts

        int base = 1;  // Current power of 2
        int offset = 1;  // Offset index for smaller numbers
        
        for (int i = 1; i <= n; i++) {
            if (i == base) {  // Check for power of 2
                ans[i] = 1;
                base <<= 1;  // Update to the next power of 2
                offset = 1;  // Reset offset for smaller numbers
            } else {
                ans[i] = ans[offset] + 1;  // Use previously computed value
                offset++;  // Move to the next number
            }
        }

        return ans;
    }
}

Python

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans: List[int] = [0] * (n + 1)  # Result array to store counts

        base: int = 1  # Current power of 2
        offset: int = 1  # Offset index for smaller numbers
        
        for i in range(1, n + 1):
            if i == base:  # Check if i is a power of 2
                ans[i] = 1
                base <<= 1  # Update to the next power of 2
                offset = 1  # Reset offset for smaller numbers
            else:
                ans[i] = ans[offset] + 1  # Use previously computed value
                offset += 1  # Move to the next number

        return ans

Complexity

• ⏰ Time complexity: O(n). The loop iterates from 1 to n, and all operations inside are constant time.
• 🧺 Space complexity: O(n), An array ans of size n + 1 is used to store results.

Method 3 - DP

To solve this problem using Dynamic Programming (DP), the key insight is to utilise previously computed results to calculate the number of 1’s for the current number.

$$ ans[i] = ans[i \gg 1] + (i & 1) $$

• i >> 1: This shifts the number i to the right by 1 bit (essentially dividing i by 2), leveraging previously computed results.

• (i & 1): Checks if the last bit of i is 1 (whether i is odd).

• ans[0] = 0 (base case, 0 has no set bits).

• For each number i from 1 to n, compute ans[i] using the transition function above.

Transitions

• If i is even: There is no additional 1 in its binary representation compared to i >> 1.
• If i is odd: There is exactly one additional 1 compared to i >> 1.

Code

Java

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];  // DP table to store number of set bits

        for (int i = 1; i <= n; i++) {
            // Transition: ans[i >> 1] gives the count for i // 2, and (i & 1) adds 1 if i is odd
            ans[i] = ans[i >> 1] + (i & 1);
        }

        return ans;
    }
}

Python

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans: List[int] = [0] * (n + 1)  # DP table to store number of set bits
        
        for i in range(1, n + 1):
            # Transition: ans[i // 2] gives the count for i >> 1, and (i & 1) adds 1 if i is odd
            ans[i] = ans[i >> 1] + (i & 1)
        
        return ans

Complexity

• ⏰ Time complexity: O(n). The loop runs for n computations, and each computation takes constant time, hence it is O(n).
• 🧺 Space complexity: O(n) used by dp array.

Dry Run

• Base Case:
  • ans[0] = 0: The number 0 contains no 1’s in its binary representation.
• Transition:
  • ans[i >> 1]: Uses the previously computed value for i >> 1 (which is floor division by 2).
  • (i & 1): Adds 1 if the current number i is odd (its least significant bit is 1).
• Why Efficient?:
  • Instead of recalculating the binary representation of numbers from scratch, the DP approach reuses previously computed results.

Let’s compute countBits(10) step by step:

Method 4 - Using the Recurrence Relation

The solution leverages a recurrence relation to calculate the count of 1s for each number:

1. For any number i:
   • If i is odd: The number of set bits is 1 more than the count of set bits in i / 2. This is because the least significant bit (rightmost bit) of an odd number is always 1 (e.g., 3 -> 11 in binary, 5 -> 101).
   • If i is even: The number of set bits is the same as in i / 2. This is because the rightmost bit is 0 for even numbers (e.g., 2 -> 10 in binary, 4 -> 100).
2. Using a recurrence relation: $ans[i] = ans[i / 2] + (i & 1)$ Here:
   • ans[i / 2] gives the count from the previously computed result.
   • (i & 1) adds 1 if the number is odd, otherwise adds 0.
3. The recurrence allows us to efficiently calculate the number of set bits incrementally for all numbers up to n.

Code

Java

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1]; // Array to store the number of 1's for each number

        ans[0] = 0; // Base case: 0 has no set bits

        for (int i = 1; i <= n; i++) {
            // If odd: Add 1 to the count of set bits of i / 2
            // If even: The count is the same as i / 2
            ans[i] = ans[i / 2] + (i & 1);
        }

        return ans;
    }
}

Python

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans: List[int] = [0] * (n + 1)  # Array to store the results

        ans[0] = 0  # Base case: 0 has no set bits

        for i in range(1, n + 1):
            # If odd: Add 1 to the count of set bits of i // 2
            # If even: The count is the same as i // 2
            ans[i] = ans[i // 2] + (i & 1)

        return ans

Complexity

• ⏰ Time complexity: O(n). The loop runs from 1 to n, and each computation takes constant time.
• 🧺 Space complexity: O(n). We maintain an array to store the results for all numbers up to n.