Problem statement

https://binarysearch.com/problems/Perfect-Squares/

Solution

Equal to Leetcode 0279. Perfect Squares.

Complexity

It is O(sqrt(n)) here for time and space.

Code

class Solution:
    def solve(self, n):
        if int(sqrt(n))**2 == n: return 1
        for j in range(int(sqrt(n)) + 1):
            if int(sqrt(n - j*j))**2 == n - j*j: return 2
            
        while n % 4 == 0: 
            n >>= 2
        if n % 8 == 7: return 4
        return 3