338. Counting Bits #

Problem #

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

Example 1:

Input: 2
Output: [0,1,1]

Example 2:

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

Follow up:

• It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Problem Summary #

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

Solution Ideas #

• Given a number, calculate the number of 1 bits in the binary representation of each number in 0 ≤ i ≤ num.

• This problem uses classic binary bit operations.

    X&1==1or==0, you can use X&1 to determine parity, X&1>0 means odd.
    X = X & (X-1) clears the lowest 1 bit
    X & -X => gets the lowest 1 bit 
    X&~X=>0
  

Code #

package leetcode

func countBits(num int) []int {
	bits := make([]int, num+1)
	for i := 1; i <= num; i++ {
		bits[i] += bits[i&(i-1)] + 1
	}
	return bits
}