Intervue featured on Shark TankIntervue featured on Shark Tank - mobile banner

Given an integer n, return an array of the number of 1 bits in the binary representation of all numbers in the range [0, n].

Constraints:

  • 0 <= n <= 10^5
  • The input will be a single integer n.

Examples:

Input: 2

Output: [0,1,1]

Explanation: The binary representation of 0 is 0, 1 is 1, and 2 is 10. Therefore, the number of 1 bits in the binary representation of all numbers in the range [0, 2] is [0, 1, 1].

Input: 5

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

Explanation: The binary representation of 0 is 0, 1 is 1, 2 is 10, 3 is 11, 4 is 100, and 5 is 101. Therefore, the number of 1 bits in the binary representation of all numbers in the range [0, 5] is [0, 1, 1, 2, 1, 2].

Solutions

Dynamic Programming

Time: O(n)Space: O(n)

The idea is to use dynamic programming to store the number of 1 bits in the binary representation of all numbers in the range [0, n]. For each number i, we can calculate the number of 1 bits by shifting the bits of i to the right by 1 and adding the least significant bit of i.


def countBits(n):
    res = [0] * (n + 1); for i in range(1, n + 1):
        res[i] = res[i >> 1] + (i & 1); return res

Difficulty: Easy

Category: Bit Manipulation

Frequency: High

Company tags:

GoogleAmazonMicrosoft