Counting Bits

Easy

The problem

For every number i from 0 to n, count the 1s in the binary form of i. Return a slice of length n + 1 where position i holds that count.

Example 1
Input: n = 2
Output: [0, 1, 1]
0 is 0, 1 is 1, 2 is 10.
Example 2
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
3 is 11, 4 is 100 and 5 is 101.

Limits

0 ≤ n ≤ 100,000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

The bit count of i is related to the count of a smaller number.

The idea

bits[i] = bits[i >> 1] + (i & 1).

Target: O(n) time

Go function shape

func countBits(n int) []int

Reference solution

Tested with go test. Try it yourself first, then compare.

// HammingWeight: n & (n-1) clears the lowest set bit, so the loop runs once per 1-bit.
func HammingWeight(n uint32) int {
	count := 0
	for n != 0 {
		n &= n - 1
		count++
	}
	return count
}

// CountBits: bits of i = bits of i/2 (shift right) plus its last bit.
func CountBits(n int) []int {
	bits := make([]int, n+1)
	for i := 1; i <= n; i++ {
		bits[i] = bits[i>>1] + i&1
	}
	return bits
}

Read the lesson: Bit Manipulation & Math