Leetcode 338. Counting Bits

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/