# Leetcode 338. Counting Bits

0

목록 보기
37/42

## Brutal Force

class Solution:
def countBits(self, num: int) -> List[int]:
keep = []
bitCounter = [0]

if num == 1: return [0, 1]

for i in range(1, num+1):
j = i

while j >= 1:

if j%2 == 1: keep.append(j % 2)

j//=2

if j == 1:
keep.append(1)
break

bitCounter.append(sum(keep))
keep = []
print(bitCounter)

return bitCounter

## O(n) Solution

2진수에서 1의 갯수를 구하다보니 패턴이 있다는 것을 알게됐다.

num 0: 0
num 1: 1

num 0 ~ 1의 수에 1을 더하면,

num 2: 10 -> 1
num 3: 11 -> 2

num 0 ~ 3의 수에 1을 더하면,

num 4: 100 -> 1
num 5: 101 -> 2
num 6: 110 -> 2
num 7: 111 -> 3

...
num 1024: 1
num 1025: 2
...

# base [0]
# nums 1: nums0 + nums0(+1)
# nums 2: nums1 + nums1(+1)
# nums 3: nums2 + nums2[:len(nums2)-1](+1)
# nums 4: nums2 + nums2(+1)
# nums 5: nums4 + nums4[:1](+1)
# nums 6: nums4 + nums4[:2](+1)
# nums 7: nums4 + nums4[:3](+1)
class Solution:
def countBits(self, num: int) -> List[int]:
prev = [0]

k = 1

while k*2 <= num:
k *= 2 # 2, 4, 8 ...
prev = prev + [j+1 for j in prev]
target = k
return prev + [k+1 for k in prev[:num-target+1]]

https://leetcode.com/problems/counting-bits/