Counting Bits

1. Problem Description

Given a non-negative integer num. For every number i in the range 0 ≤ i ≤ num, calculate the number of 1s in its binary representation and return them as an array.

2. Approach

1. Approach 1
   • AND with 1
2. Approach 2
   1. Odd and even

3. Implementation

3.1. AND with 1

package main

func countBits(num int) []int {
	res := make([]int, 0)
	for i := 0; i <= num; i++ {
		res = append(res, countBit1(i))
	}

	return res
}

func countBit1(num int) int {
	bit := 1
	count := 0
	for i := 0; i < 32; i++ {
		if num&bit != 0 {
			count++
		}
		bit <<= 1
	}
	return count
}

3.2. Odd and Even

func countBits(n int) []int {
    res := make([]int, n+1)
    for i := 1; i <= n; i++ {
        if i % 2 == 1 {
            res[i] = res[i-1]+1
        }else {
            res[i] = res[i/2]
        }
    }
    return res
}

4. References

• A Clear Approach - Counting Bits - LeetCode
• Counting Bits - Counting Bits - LeetCode