class Solution {
    public int[] countBits(int n) {
        int[] counts = new int[n + 1];
        counts[0] = 0;

        for (int i = 1; i < counts.length; i++) {
            if ((i & 1) == 1) { // odd
                // an odd number ends in 1 binary.
                // if you subtract one, it ends in 0 binary.
                // so you take the count of the previous plus one,
                counts[i] = counts[i - 1] + 1;
            }
            else {
                // an even number ends in 0 binary.
                // the count of ones is the same as the number
                // with bits shifted to the right.
                // e.g. 0110 -> 0011
                //      (6) ->  (3)
                counts[i] = counts[i >> 1];
            }
        }

        return counts;
    }
}