Solution: Counting Bits

Let's solve the Counting Bits problem using the Dynamic Programming pattern.

We'll cover the following

Statement

For a given positive integer, n, your task is to return an array of length n+1n+1 such that for each xx where 0≤x≤n0 \leq x \leq n, result[x] is the count of 11s in the binary representation of xx.

Constraints:

  • 0≤n≤1040 \leq n \leq 10^4

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach for this solution would be to iterate through the string character by character. During the traversal, we convert each number to its binary representation, count the number of 11 bits in each binary representation, and store the result in an array.

This approach would have a time complexity of O(nlog⁡n)O(n \log n) and a space complexity of O(n)O(n).

Optimized approach using dynamic programming

The problem involves using a dynamic programming approach to calculate and store the count of 11 bits and use it for future iterations. Let’s take an example to see how the previous count of 11 bits helps to find the count of 11 bits in future iterations.

Press + to interact
Relation of even and odd binary representation of integers
Relation of even and odd binary representation of integers

For every digit, we know it can be an even number or an odd number. Let’s see how we can compute each by using binary manipulation:

  1. For even numbers, the count can be calculated using the count for half of that number. For example, the count of 11 bit for 66 equals the count of 11 bit for 33. We can confirm this by looking at the binary representation of 66 and 33, which are 01100110 and 00110011, respectively. The count of 11 bit is two in both numbers.

  2. For odd numbers, the count is one more than the count for half of that number. For example, the count of 11 bit for 77 equals the count of 11 bit for (7/2)=3+1(7/2) = 3 + 1 extra bit. We can confirm this by looking at the binary representation 77 of and 33, which are 01110111 and 0011+10011 + 1, respectively. The final count of 11 bit after adding an extra 11 bit to the half number is three.

Now, let’s look at the basic algorithm to solve this problem:

  1. Add base cases where the 0th0^{th} and 1st1^{st} iteration results will be 00 and 11.

  2. Create a 1D table of length n+1n+1 containing all zeros. This will be used to store and recalculate the count of the 11 bits in future iterations.

  3. Next, we’ll iterate through the range of numbers from 22 to nn. If the number is even for each number in the range, compute result[x] = result[x / 2]. If the number is odd, compute result[x] = result[x / 2] + 1.

  4. Finally, return the list containing the number of set bits in the binary representation of the numbers from 00 to nn.

The following illustration shows these steps in detail:

Let’s look at the code for this solution below:

public class CountBits {
    public static int[] countingBits(int n) {
        int[] result = new int[n + 1];
        if (n == 0) {
            return result;
        }
        result[0] = 0;
        result[1] = 1;
        for (int x = 2; x <= n; ++x) {
            if ((x % 2) == 0) {
                result[x] = result[x / 2];
            }
            else {
                result[x] = result[x / 2] + 1;
            }
        }
        return result;
    }
    // Driver code
    public static void main(String[] args) {
        int[] inputBits = { 1, 2, 3, 4, 5, 10 };
        for (int i = 0; i < inputBits.length; ++i) {
            System.out.println((i + 1) + ".\t Bits: " + inputBits[i]);
            int[] result = countingBits(inputBits[i]);
            System.out.println("\t Counting bits: " + java.util.Arrays.toString(result));
            System.out.println(new String(new char[100]).replace("\0", "-"));
        }
    }
}
Counting Bits

Solution summary

The solution above can be summarized in the following points:

  • A DP array is created to store the result of any subproblems encountered during iteration.

  • During the iteration, we performed two checks for even and odd numbers:

    • If the current number is even, then search and replace the current index’s value of the DP array with the value stored at half of this number. This is because both digits will have the same number of 11 bits.

    • Otherwise, add an additional 11 bit in the case of odd numbers.

  • Return the last index of the DP array containing the number of set bits in the binary representation of the numbers from 00 to nn.

Time complexity

The time complexity of this solution is O(n)O(n) because the number of operations required for each integer xx within the range of 11 to nn is constant and is not affected by the number of bits in xx.

Space complexity

The space complexity of this solution is O(1)O(1).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.