Counting Bits
Problem
Given an integer n
, return an array ans
of length n + 1
such that for each i
(0 <= i <= n
), ans[i]
is the number of 1
’s in the binary representation of i
.
Follow up:
- It is very easy to come up with a solution with a runtime of
O(n log n)
. Can you do it in linear timeO(n)
and possibly in a single pass? - Can you do it without using any built-in function (i.e., like
__builtin_popcount
in C++)?
Constraints
0 <= n <= 105
Solution
The problem Counting Bits
can be solved using a dynamic programming. Let binary representation of n
as a1a2...ak
where ak = 0, 1
. Then, binary representation of n / 2
can be expressed as 0a1a2...ak-1
. Thus, number of 1
’s for n
is the same as n / 2
except for the least significant bit. In other words, S(n) = S(n / 2) + (n mod 2)
holds true where S(n)
is the total number of 1
’s in the binary representation of n
.
Implementation
class Solution
{
public:
vector<int> countBits(int n)
{
vector<int> ret(n + 1, 0);
for (int i = 1; i <= n; i++)
ret[i] = ret[i >> 1] + (i & 1);
return ret;
}
};