Counting Bits

NeetCode: Counting Bits · LeetCode: 338. Counting Bits · Difficulty: Easy

Given n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in i.

Example

Text

Input:  n = 5    Output: [0, 1, 1, 2, 1, 2]

Brute force: count each number independently

For every i from 0 to n, count its set bits with Kernighan's loop: x & (x - 1) clears the lowest set bit, so the loop runs once per set bit. That is a fresh O(log i) computation per number.

Java

import java.util.Arrays;

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int x = i;
            int c = 0;
            while (x > 0) {
                x &= x - 1;
                c++;
            }
            ans[i] = c;
        }
        return ans;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.countBits(5)));
        System.out.println(Arrays.toString(s.countBits(0)));
        System.out.println(Arrays.toString(s.countBits(8)));
    }
}

Output

[0, 1, 1, 2, 1, 2]
[0]
[0, 1, 1, 2, 1, 2, 2, 3, 1]

Time: O(n log n). Space: O(1) besides the output.

Optimal: reuse the answer for i / 2

Dropping the lowest bit of i (i >> 1) gives a smaller number whose answer is already computed, and the dropped bit is i & 1. So bits[i] = bits[i >> 1] + (i & 1). Each entry costs one lookup and one addition.

i	binary	`bits[i >> 1]`	`i & 1`	`bits[i]`
3	`11`	`bits[1] = 1`	1	2
4	`100`	`bits[2] = 1`	0	1
5	`101`	`bits[2] = 1`	1	2

Java

import java.util.Arrays;

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1]; // bits[0] is 0 because a new int array is zero-filled
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.countBits(5)));
        System.out.println(Arrays.toString(s.countBits(0)));
        System.out.println(Arrays.toString(s.countBits(8)));
    }
}

Output

[0, 1, 1, 2, 1, 2]
[0]
[0, 1, 1, 2, 1, 2, 2, 3, 1]

Time: O(n). Space: O(1) besides the output array.