Counting Bits
Statement
Given a positive integer n, return an array of length n + 1 such that for each x where 0 ≤ x ≤ n, result[x] is the number of 1s in the binary representation of x.
Constraints
- 0 ≤
n≤ 10⁴
Solution
"""
production algorithm
"""
from math import floor, log
class Solution:
def counting_bits(self, n):
"""
time complexity O(n)
space complexity O(n)
"""
memo = [0 if k == 0 else None for k in range(n + 1)]
for k in range(1, n + 1):
memo[k] = 1 + memo[k - 2**floor(log(k, 2))]
return memo"""
unit tests
"""
from unittest import TestCase
from algorithms.dynamic_programming.counting_bits.solution import Solution
class SolutionTestCase(TestCase):
def test_n_is_base_case(self):
# Given
n = 0
solution = Solution()
# When
actual = solution.counting_bits(n)
# Then
expected = [0]
self.assertEqual(actual, expected)
def test_n_is_not_base_case(self):
# Given
n = 15
solution = Solution()
# When
actual = solution.counting_bits(n)
# Then
expected = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4]
self.assertEqual(actual, expected)Strategy
Dynamic Programming.
Explanation
A 1-D matrix, whose dimension is x, is maintained to hold the solution for x seen so far. In the trivial case, where x is 0, the solution is 0. Then, iteration of x occurs. The solution for smaller x is used to find the solution for larger x. Iteration ends when the solution has been found for the input n.
Notice, that the problem has optimal substructure, i.e. the solution of larger x can be found from the solution of smaller x. Also notice, that the problem has overlapping subproblems, i.e. the solution of smaller x can be reused to find the solution of multiple distinct larger x. Since the problem has optimal substructure and overlapping subproblems, then dynamic programming can be used to solve the problem.
Time Complexity
The time complexity of the algorithm is O(n).
Space Complexity
The auxiliary space complexity of the algorithm is O(1).
