ほぼ日刊競プロ leetcode　338. Counting Bits

338. Counting Bits

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.

考えたこと

以下の３パターンを考えた．
１．２進数に変換して文字列に同士の和をとる．
２．２進数に変換して10で割ったあまりの和をとる．
３．２進数に変換して１が出てきた数をカウントする．

1

class Solution:
   def countBits(self, n: int) -> List[int]:
       ans = []
       for i in range(n+1):
           ans.append(sum(list(map(int, str(bin(i)[2:])))))
       return ans

2

class Solution:
   def countBits(self, n: int) -> List[int]:
       def digit_sum(n):
           # 各桁の和を求める
           # 計算量: O(logN)
           ans = 0
           while n > 0:
               ans += n % 10
               n //= 10
           return ans
       ans = []
       for i in range(n+1):
           ans.append(digit_sum(int(bin(i)[2:])))
       return ans

3

class Solution:
   def countBits(self, n: int) -> List[int]:
       temp = [bin(i).count("1") for i in range(n+1)]
       return temp

2->1->3の順で計算時間が短かった．