Number of 1 bits
July 16, 2022
bit-manipulationProblem URL: Number of 1 bits
We can have a repeatative pattern if we look at the most significant bit. For example, lets look the following table-
Number | Binary |
---|---|
0 | 000 |
1 | 001 |
2 | 010 |
3 | 011 |
4 | 100 |
5 | 101 |
6 | 110 |
7 | 111 |
For first 2 number, most significant bit is different, and it 0 and 1. Then next 2 numbers, most significant bit is same but the rest is similar to first 2 number. For the next 4 number, msb is same, and rest is same as previous 4 numbers and so on. So, we can calculate on that.
class Solution:
def countBits(self, n: int) -> List[int]:
dp = [0] * (n+1)
offset = 1
for i in range(1, n+1):
if offset * 2 == i:
offset = i
dp[i] = 1 + dp[i-offset]
return dp
We iterate through the array only once so, the time complexity is O(n)
. We don't use any extra space, we use the same return array to calculate, so space complexity is O(1)
.