Vultr DocsLatest Content

Counting Bits

Updated on 09 May, 2025
Counting Bits header image

Problem Statement

In this computational problem, you are tasked with generating a list called ans of size n + 1, where n is a non-negative integer provided as input. Each element ans[i] in this list should represent the count of '1's in the binary representation of the integer i. For example, for any index i, if you convert i to its binary form, the value at ans[i] should be the total number of '1' bits in that binary form.

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

Constraints

  • 0 <= n <= 105

Approach and Intuition

To tackle this problem, the key is understanding binary representation and bit manipulation. Here's a step-by-step breakdown of how one might approach this:

  1. Initialize an Array: Start by creating an array ans of size n + 1 to hold the count of 1's for every number from 0 to n.

  2. Iterate Through Numbers: Loop through all numbers from 0 to n. For each number:

    • Convert the number to its binary form or use bit manipulation to count the 1's directly.
    • Store the count of 1's in the respective index of the array ans.

  3. Return the Array: Once all numbers are processed, return the ans array.

This method ensures that the problem constraints are adhered to, efficiently counting the number of 1's in the binary representation of each number up to n.

Analysis of Examples:

  • In Example 1, with n = 2:

    • Binary of 0 is 0 —> 0 ones.
    • Binary of 1 is 1 —> 1 one.
    • Binary of 2 is 10 —> 1 one.
    • Thus, the output is [0, 1, 1].

  • In Example 2, with n = 5:

    • We analyze each number from 0 to 5 and count the 1's as demonstrated for n=2.
    • Resulting output is [0, 1, 1, 2, 1, 2].

This strategy efficiently and correctly solves the problem using fundamental programming concepts and knowledge of binary systems.

Solutions

  • Java
  • Python
java 
public class Solution {
    public int[] bitCounting(int maximum) {
        int[] result = new int[maximum + 1];
        for (int i = 1; i <= maximum; ++i) {
            result[i] = result[i & (i - 1)] + 1;
        }
        return result;
    }
}

The Java solution provided employs a dynamic programming approach to solve the problem of counting the number of 1's (bits set to high) for each number up to a given maximum. The method bitCounting(int maximum) initializes an array result of size maximum + 1 to store the bit counts for all numbers from 0 to maximum.

Iterate through each number starting from 1 to maximum. Utilize the relation result[i] = result[i & (i - 1)] + 1 to compute the number of 1's in the binary representation of i. This calculation effectively reduces the problem by stripping off the last set bit of i until it reaches zero, which efficiently counts the bits by building on previously computed results.

Finally, the function returns the result array, which contains the count of set bits for each number from 0 to maximum. This method leverages properties of bitwise operations to achieve an efficient solution with a better than naive computational complexity.

python 
class Solution:
    def bitsCount(self, number: int) -> List[int]:
        result = [0] * (number + 1)
        for i in range(1, number + 1):
            result[i] = result[i & (i - 1)] + 1
        return result

The provided solution offers an efficient way to generate an array where each element at index i contains the count of 1's in the binary representation of the integer i. The code leverages Brian Kernighan's algorithm to count bits, which uses a trick for clear the least significant bit of a number to gradually reduce it to zero, counting the operations in the process. Follow these key points when executing the algorithm in Python:

  • Initialize a list result of size number + 1 with all elements set to 0.
  • Iterate through numbers from 1 to number.
  • For each number, calculate the number of set bits by using the expression result[i] = result[i & (i - 1)] + 1. This expression counts the bits by stripping the lowest set bit at each step.
  • Finally, return the result list, which contains the bit counts for all numbers from 0 to number.

This method efficiently fills up the result array with the count of set bits for each index, offering a time complexity close to linear relative to the number of input integers, making it suitable for large values of number.

Comments