LC279. Perfect Squares

class Solution:
    def numSquares(self, n: int) -> int:
        """ tc O(NlnN)  sc O(N)
        """
        # dp[i]: given number is i, the least number of perfect squares that sum to i
        dp = [n]*(n+1)
        dp[0] = 0
        for x in range(1,n+1):
            i = 1
            for i in range(1,int(sqrt(x))+1):
                dp[x] = min(dp[x],dp[x-i**2]+1)   #use while loop will cause TLE 
        return dp[-1]

class Solution:
    def numSquares(self, n: int) -> int:
        """ tc O(N^h/2)  sc O(sqrt(N)**h)   h: wirst case sqrt(N), sc means for a N-ary tree, max # can appear in level h 
        BFS solution
        main idea: consider a graph consisting of 0,... n as its node, node u is connected with node v via an edge if on only if u = v + i**2  
        1. create queue, seen set, set offset 0, initialize its level as 0
        2. each round of q, loop through possible perfect squares i**2, add it with node in q =>  v = u + i^2
        3. there are 3 cases: (1) v == n (2) v > n:  (3) v < n ; for case (1), shows we find the minimun level, so we can return directly; case (2) shows there is no case v can equal to n since v will keep increasing; for (3), there is still potential can be summed up to n so we push unseen v in the queue and mark the value to prevent repeated operation
        """
        q = collections.deque()
        q.append(0)
        seen = set()
        seen.add(0)
        level = 0
        while q:
            size = len(q)
            level += 1 
            for _ in range(size):
                u = q.popleft()
                for i in range(1,int(sqrt(n))+1):
                    v = u + i**2    
                    if v == n:
                        return level
                    if v > n: # early termination
                        break
                    if v not in seen:
                        seen.add(v)
                        q.append(v)
        return level
                

class Solution:
    def numSquares(self, n: int) -> int:
        """ tc O(sqrtN)  sc O(1)
        main idea: based on lagrange's four square theorm, any num = 4^k*(8m+7)
        """
        def is_sq(v):
            rt = int(sqrt(v))
            return rt**2 == v 
        if is_sq(n):
            return 1 
        # 2 
        for i in range(1,int(sqrt(n)+1)):
            v = n - i**2
            if v < 0:
                break
            if is_sq(v):
                return 2
        # 4
        while n%4 == 0 #n &3 == 0:  
            n >>= 2
        if n%8 == 7 #n&7 == 7   
            return 4
        return 3