Skip to content

Number Theory Others

Table of Contents

326. Power of Three

633. Sum of Square Numbers

279. Perfect Squares

import math


# DP - Knapsack Unbounded
def numSquares(n: int) -> int:
    dp = [float("inf") for _ in range(n + 1)]
    dp[0] = 0

    for i in range(1, n + 1):
        for j in range(1, int(math.sqrt(n)) + 1):
            dp[i] = min(dp[i], dp[i - j**2] + 1)

    return dp[n]


n = 12
print(numSquares(n))  # 3

1015. Smallest Integer Divisible by K

2240. Number of Ways to Buy Pens and Pencils

2221. Find Triangular Sum of an Array

Comments