LeetCode problem#338

Counting Bits

Solved in 1 languageJava

25 lines

1class Solution {
2    public int[] countBits(int n) {
3        int[] counts = new int[n + 1];
4        counts[0] = 0;
5
6        for (int i = 1; i < counts.length; i++) {
7            if ((i & 1) == 1) { // odd
8                // an odd number ends in 1 binary.
9                // if you subtract one, it ends in 0 binary.
10                // so you take the count of the previous plus one,
11                counts[i] = counts[i - 1] + 1;
12            }
13            else {
14                // an even number ends in 0 binary.
15                // the count of ones is the same as the number
16                // with bits shifted to the right.
17                // e.g. 0110 -> 0011
18                //      (6) ->  (3)
19                counts[i] = counts[i >> 1];
20            }
21        }
22
23        return counts;
24    }
25}

How it works

The provided solution is for the problem of counting the number of 1s (bits that are set) in the binary representation of all numbers from 0 to n. The method employed utilizes dynamic programming to efficiently compute the results. Let's break down the implementation step by step:

Class and Method Definition

class Solution {
    public int[] countBits(int n) {

We define a class named Solution, and within it, a public method countBits that accepts an integer n which is the upper limit (inclusive) for which we want to count the bits.

Initialize the Array

    int[] counts = new int[n + 1];
    counts[0] = 0;

We create an integer array counts of size n + 1 to store the count of 1s for each number from 0 to n.
We initialize counts[0] to 0 because the binary representation of 0 has zero bits set.

Fill the Counts Array

    for (int i = 1; i < counts.length; i++) {

We iterate through all numbers from 1 to n.
Within each iteration, we determine if the current number i is odd or even:

        if ((i & 1) == 1) { // odd

Case for Odd Numbers

If i is odd (i.e., the least significant bit is 1), we can observe that:
- An odd number in binary ends with 1. For example 1 (01), 3 (11), 5 (101), etc.
- If we subtract 1 from it, it becomes an even number (which ends with 0).

Thus:

            counts[i] = counts[i - 1] + 1;

We can derive the count of 1s for the odd number i from the count of 1s of the previous number i - 1 (which has the same number of 1s as i except it loses the 1 from the LSB), then add 1 to it (for the 1 bit that i has at the end).

Case for Even Numbers

        } else { // even
            counts[i] = counts[i >> 1];

If i is even (with least significant bit 0), its binary representation can be thought to be like shifting right to remove the last 0.
We can find the count of 1s of this number by looking at the number derived by right shifting i, which is i >> 1.
For instance, 6 (0110) shifts to 3 (0011), and thus the count of 1s is the same as the count of 1s in 3.

Return the Result

    }
    return counts;
}

Finally, we return the counts array, which now contains the number of 1s for each number from 0 to n.

Complexity

Time Complexity: (O(n)), since we only loop through numbers from 1 to n once.
Space Complexity: (O(n)), due to the usage of an additional array to store the counts.

Conclusion

This solution smartly leverages properties of binary numbers, particularly focusing on the odd/even nature of numbers and their relationships, effectively resulting in a very efficient way to count the bits.

Written by AI from the code above, so double-check anything important.

All problems

Problem statements belong to LeetCode and are on leetcode.com. We're not affiliated with LeetCode.