338-Counting-Bits.py

'''Leetcode- https://leetcode.com/problems/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.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
'''

# Bit manipulation approach
defcountBits(self, n):
ans= []
foriinrange(n+1):
cur=0
whilei:
cur+=i&1
i>>=1
ans.append(cur)
returnans

# T:O(NlogN)
# S:O(N)

#DP way
defcountBits(self, n):
dp= [0]*(n+1)
offset=0

foriinrange(1,n+1):
ifoffset*2==i:
offset=i
dp[i] =1+dp[i-offset]
returndp

# T:O(N)
# S:O(N)