[LeetCode] 338. Counting Bits

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:
For num = 5 you should return [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.

Hint:

1. You should make use of what you have produced already.
2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
3. Or does the odd/even status of the number help you in calculating the number of 1s?

Thought process:

GCC has a built-in function called "__builtin_popcount", which can return the number of 1 bits of an integer in constant time.

Solution 1:

1 2 3 4 5 6 7 8 9 10 11 12

class Solution { public: vector<int> countBits(int num) { vector<int> bits; for (int i = 0; i <= num; i++) { bits.push_back(__builtin_popcount(i)); } return bits; } };

Time complexity: O(n), where n = num.

This solution is quite trivial. Another idea is to test a number's least significant bit, right shift the number by 1, and repeat until the number == 0.

Solution 2:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: vector<int> countBits(int num) { vector<int> bits; for (int i = 0; i <= num; i++) { int j = i; int count = 0; while (j > 0) { if (j & 1) { count++; } j >>= 1; } bits.push_back(count); } return bits; } };

Time complexity: O(nlogn).

Follow-up:

This problem can actually be solved using dynamic programming. The function is: f[n] = f[n / 2] + n % 2.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12

class Solution { public: vector<int> countBits(int num) { vector<int> bits(num + 1); for (int i = 1; i <= num; i++) { bits[i] = bits[i / 2] + (i % 2); } return bits; } };

Time complexity: O(n).
Space complexity: O(n).