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:

1
2
3
4
5
6

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

1
2
3
4
5
6
7
8
9

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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 - DP following power of 2

This method focuses on leveraging the properties of powers of 2. Every power of 2 (2^m) has exactly one set bit in its binary representation at mth position. Non-power-of-2 numbers can be expressed as:

1

i = 2^m + r

where r is the remainder. By observing this, we can relate the set bits of these numbers to their remainder.

Now, suppose n = 10. For that lets look at the numbers from 1 to 10:

So, dp[0] = 0 is the base case.

Here’s how the recurrence relation applies:

• dp[0] = 0 (base case)
• dp[1] = dp[0] + 1 ⇨ 1 + dp[i - 1]
• dp[2] = dp[0] + 1 ⇨ 1 + dp[i - 2]
• dp[3] = dp[1] + 1 ⇨ 1 + dp[i - 2]
• dp[4] = dp[0] + 1 ⇨ 1 + dp[i - 4]
• dp[5] = dp[1] + 1 ⇨ 1 + dp[i - 4]
• dp[6] = dp[2] + 1 ⇨ 1 + dp[i - 4]
• dp[7] = dp[3] + 1 ⇨ 1 + dp[i - 4]
• dp[8] = dp[0] + 1 ⇨ 1 + dp[i - 8]
• dp[9] = dp[1] + 1 ⇨ 1 + dp[i - 8]
• dp[10] = dp[2] + 1 ⇨ 1 + dp[i - 8]

The offset corresponds to the nearest power of 2 for each number. As soon as we reach the next power of 2 (2, 4, 8, ...), we update the offset to that power of 2. This avoids recalculating results unnecessarily.

Using this insight, we can iterate through numbers from 1 to n (starting with the base case dp[0] = 0) and compute the count of set bits for each number using this recurrence formula:

$$ dp[i] = dp[i - offset] + 1 $$

Where offset is the largest power of 2 less than or equal to i.

Approach

• Use dynamic programming to compute set bits iteratively by tracking the offset, which is the largest power of 2 less than or equal to the current number.
• For each number i, use the recurrence relation: $$ dp[i] = dp[i - offset] + 1 $$ Here, offset corresponds to 2^m, the largest power of 2 encountered so far.
• Incrementally compute results by reusing those from smaller subproblems (numbers closer to powers of 2).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	public int[] countBits(int n) {
		int[] dp = new int[n + 1];
		int offset = 1;
		for (int i = 1; i < n + 1; i++){
			if (offset * 2 == i){
				offset *= 2;
			}
			dp[i] = dp[i - offset] + 1;
		}
		return dp;
	}
}

1
2
3
4
5
6
7
8
9

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp: List[int] = [0] * (n + 1)
        offset: int = 1
        for i in range(1, n + 1):
            if offset * 2 == i:
                offset *= 2
            dp[i] = dp[i - offset] + 1
        return dp

Complexity

• ⏰ Time complexity: O(n). The algorithm iterates through numbers from 1 to n, performing a constant-time calculation for each number based on the recurrence relation. Thus, the time complexity is O(n).
• 🧺 Space complexity: O(n). The algorithm uses an array dp of size n + 1 to store the set bit counts for each number. Hence, the space complexity is O(n).

Method 3 - Using DP based on division by 2

We can refine the solution further by focusing solely on how the number x changes after dividing the number by 2 which is same as right shifting the number by 1.  

Lets take 2 numbers x and y where x / 2 = y. Now, there are 2 main cases.

1. Case 1: x is Even
   • When x is even, its least significant bit (LSB) is 0.
   • Dividing x by 2 (or right-shifting it) gives y, which has the same number of set bits as x.
   • For example:
     • x = 6 (110) and y = 3 (011)
     • 6 / 2 = 3
     • Both 6 and 3 have the same number of set bits (2 set bits in this case).
2. Case 2: x is Odd
   • When x is odd, its least significant bit (LSB) is 1.
   • Dividing x by 2 (or right-shifting it) gives y, and the number of set bits in x is 1 more than in y.
   • For example:
     • x = 7 (111) and y = 3 (011)
     • 7 / 2 = 3
     • Number of set bits in 7 = 3, while Number of set bits in 3 = 2.

From these cases, we can define the recurrence relation as:

$$ dp[i] = dp[i/2] + i \mod 2 $$

This uses simple arithmetic to determine whether the least significant bit contributes an additional 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

        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
            dp[i] = dp[i / 2] + (i % 2);
        }

        return dp;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

        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
            dp[i] = dp[i / 2] + (i % 1)

        return dp

Complexity

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

Method 4 - Using DP based on division by 2 but fully bitwise

Alternatively, as shown in the Number of 1 Bits problem, we can express this with binary operators for efficiency:

$$ 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 (which checks whether i is odd).

So,

• 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.

Approach

• dp[0] = 0 (base case, 0 has no set bits).
• For each number i from 1 to n, compute dp[i] using the transition function above.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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
            dp[i] = dp[i >> 1] + (i & 1);
        }

        return ans;
    }
}

1
2
3
4
5
6
7
8
9

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
            dp[i] = dp[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.