leetcode-go/leetcode/medium/338.counting-bits.go

func countBits(num int) []int {
	res := make([]int, num+1)
	if num == 0 {
		return res
	}
	res[1] = 1
	for i, j := 2, 0; i <= num; i++ {
		if i&1 == 0 { // If i is even, bits(i) = bits(i/2)
			j++
			res[i] = res[j]
		} else { // If i is odd, bits(i) = bits(i/2) + 1
			res[i] = res[j] + 1
		}
	}
	return res
}