338. Counting Bits

  • 60.0%

https://leetcode.com/problems/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.

1
2
3
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:

You should make use of what you have produced already.

Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.

Or does the odd/even status of the number help you in calculating the number of 1s?


方法一:

i&(i-1) 是消除最小的一位1,取其个数,再加1。

考虑的是两段,最小的一位1,与这位1更新为0的数字,两段的个数的和。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res(num+1, 0);
for(int i=1; i<=num; i++){
res[i] = res[i&(i-1)] + 1;
}
return res;
}
};

方法二:

分两段求个数,一段是最后一位,一段是除最后一位的前一段。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res(num+1, 0);
res[1] = 1;
for(int i=2; i<=num; i++){
res[i] = res[i%2] + res[i/2];
}
return res;
}
};

cpp

https://discuss.leetcode.com/topic/40262/four-lines-c-time-o-n-space-o-n

Four lines, C++, time O(n), space O(n)

位运算 i&(i-1)可以出掉最低位的一位1.

i&(i-1) drops the lowest set bit. For example: i = 14, its binary representation is 1110, so i-1 is 1101, i&(i-1) = 1100, the number of “1” in its binary representation decrease one, so ret[i] = ret[i&(i-1)] + 1. (Sorry, my English is so poor and I have tried my best to make it clearly, I hope you can understand my explanation)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
vector<int> countBits(int num) {
vector<int> result(num+1, 0);
result[0] = 0;
for(int i=1; i<=num; i++)
result[i] += result[i&(i-1)] + 1;
return result;
}
};

124ms, April.24th, 2016

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
vector<int> countBits(int num) {
vector<int> result(num+1, 0);
result[0] = 0;
int i;
for(i = 1; i <= 2; i++) result[i] = 1;
for(i = 3; i <= num; i++) result[i] = result[i/2] + result[i%2];
return result;
}
};

python

https://discuss.leetcode.com/topic/45331/simple-python-solution

Simple Python Solution

Code works by constantly extending a list with itself but with the values incremented by 1.

Simple python solution that runs in O(n) time. Let me know if there are any ways to improve it.

1
2
3
4
5
6
7
8
9
10
11
12
13
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""

iniArr = [0]
if num > 0:
amountToAdd = 1
while len(iniArr) < num + 1:
iniArr.extend([x+1 for x in iniArr])

return iniArr[0:num+1]

A four liner that does the same thing as above. The above had a few redundancies.

1
2
3
4
5
6
7
8
9
10
11
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
answer = [0, 1]

while len(answer) <= num:
answer.extend(map(lambda x:x+1, answer))

return answer[:num+1]

java

https://discuss.leetcode.com/topic/40162/three-line-java-solution

An easy recurrence for this problem is f[i] = f[i / 2] + i % 2.

1
2
3
4
5
6
7
8
public class Solution {
public int[] countBits(int num) {
int[] ret = new int[1+num];
for(int i=1; i<=num; ++i)
ret[i] = ret[i>>1] + (i&1);
return ret;
}
}

1
2
3
4
5
6
7
8
public class Solution {
public int[] countBits(int num) {
int[] ret = new int[1+num];
for(int i=1; i<=num; ++i)
ret[i] = ret[i&(i-1)] + 1;
return ret;
}
}

https://discuss.leetcode.com/topic/41785/simple-java-o-n-solution-using-two-pointers

Simple Java O(n) solution using two pointers

This uses the hint from the description about using ranges. Basically, the numbers in one range are equal to 1 plus all of the numbers in the ranges before it. If you write out the binary numbers, you can see that numbers 8-15 have the same pattern as 0-7 but with a 1 at the front.

My logic was to copy the previous values (starting at 0) until a power of 2 was hit (new range), at which point we just reset the t pointer back to 0 to begin the new range.

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] countBits(int num) {
int[] ret = new int[num+1];
ret[0] = 0;
int pow = 1;
for(int i = 1, t = 0; i <= num; i++, t++) {
if(i == pow) {
pow *= 2;
t = 0;
}
ret[i] = ret[t] + 1;
}
return ret;
}

Question:
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.

Thinking:

  1. We do not need check the input parameter, because the question has already mentioned that the number is non negative.
  2. How we do this? The first idea come up with is find the pattern or rules for the result. Therefore, we can get following pattern

Index : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

num : 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

Do you find the pattern?

Obviously, this is overlap sub problem, and we can come up the DP solution. For now, we need find the function to implement DP.

dp[0] = 0;

dp[1] = dp[0] + 1;

dp[2] = dp[0] + 1;

dp[3] = dp[1] +1;

dp[4] = dp[0] + 1;

dp[5] = dp[1] + 1;

dp[6] = dp[2] + 1;

dp[7] = dp[3] + 1;

dp[8] = dp[0] + 1;

This is the function we get, now we need find the other pattern for the function to get the general function. After we analyze the above function, we can get
dp[0] = 0;

dp[1] = dp[1-1] + 1;

dp[2] = dp[2-2] + 1;

dp[3] = dp[3-2] +1;

dp[4] = dp[4-4] + 1;

dp[5] = dp[5-4] + 1;

dp[6] = dp[6-4] + 1;

dp[7] = dp[7-4] + 1;

dp[8] = dp[8-8] + 1;
..

Obviously, we can find the pattern for above example, so now we get the general function

dp[index] = dp[index - offset] + 1;

Coding:

1
2
3
4
5
6
7
8
9
10
11
public int[] countBits(int num) {
int result[] = new int[num + 1];
int offset = 1;
for (int index = 1; index < num + 1; ++index){
if (offset * 2 == index){
offset *= 2;
}
result[index] = result[index - offset] + 1;
}
return result;
}
谢谢你,可爱的朋友。