The task is simply stated. Given an integer n (3 < n < 10^(9)), find the length of the smallest list of [*perfect squares*](https://en.wikipedia.org/wiki/Square_number) which add up to n. Come up with the best algorithm you can; you'll need it!

Examples:

sum_of_squares(17) = 2  17 = 16 + 1 (4 and 1 are perfect squares).
sum_of_squares(15) = 4  15 = 9 + 4 + 1 + 1. There is no way to represent 15 as the sum of three perfect squares.
sum_of_squares(16) = 1  16 itself is a perfect square.

Time constraints:

5 easy (sample) test cases: n < 20

5 harder test cases: 1000 < n < 15000

5 maximally hard test cases: 5 * 1e8 < n < 1e9

```if:java
300 random maximally hard test cases: 1e8 < n < 1e9
```
```if:c#
350 random maximally hard test cases: 1e8 < n < 1e9
```
```if:python
15 random maximally hard test cases: 1e8 < n < 1e9
```
```if:ruby
25  random maximally hard test cases: 1e8 < n < 1e9
```
```if:javascript
100 random maximally hard test cases: 1e8 < n < 1e9
```
```if:crystal
250 random maximally hard test cases: 1e8 < n < 1e9
```
```if:cpp
Random maximally hard test cases: 1e8 < n < 1e9
```

Difficulty: interview

Starter code:

def sum_of_squares(n):
	

Solutions:
def one_square(n):
    return round(n ** .5) ** 2 == n

def two_squares(n):
    while n % 2 == 0: n //= 2
    p = 3
    while p * p <= n:
        while n % (p * p) == 0:
            n //= p * p
        while n % p == 0:
            if p % 4 == 3: return False
            n //= p
        p += 2
    return n % 4 == 1

def three_squares(n):
    while n % 4 == 0: n //= 4
    return n % 8 != 7

def sum_of_squares(n):
    if one_square(n): return 1
    if two_squares(n): return 2
    if three_squares(n): return 3
    return 4

sq=lambda n: (n**0.5)%1==0

def sum_of_squares(n):
    if sq(n): return 1
    while not n&3: n>>=2
    if n&7==7: return 4
    for i in range(int(n**0.5)+1):
        if sq(n-i*i): return 2
    return 3

from math import sqrt


def sum_of_squares(n):
    n_sqrt = int(sqrt(n))

    if n == n_sqrt * n_sqrt:
        return 1

    div, mod = divmod(n, 4)
    while mod == 0:
        div, mod = divmod(div, 4)
    if (div * 4 + mod) % 8 == 7:
        return 4

    for i in range(1, n_sqrt + 1):
        temp = n - i * i
        temp_sqrt = int(sqrt(temp))
        if temp == temp_sqrt * temp_sqrt:
            return 2

    return 3

from collections import Counter
sum_of_squares=lambda n:1 if (n**.5).is_integer() else 2 if all(not j&1 for i, j in Counter(two(n)).items() if i%4==3) else 4 if four(n) else 3

def two(n):
        j, li = 2, []
        while j * j <= n:
            if n % j: j+=1 ; continue 
            li.append(j) ; n //= j 
        return li + [[], [n]][n > 0]
def four(x):
        while x % 4 == 0 : x //= 4
        return 8 * (x // 8) + 7 == x 

import math
def sum_of_squares(n):
    final=[]
    de=0
    
    if str(math.sqrt(n))[::-1].find('.')==1:
        return 1
        
    else:
        for i in range(int(n**.5)):
            ans=[]
            de= n-int(de**.5-i)**2
            ans.append(int(de**.5))
            while de>0:
                de-=int(de**.5)**2
                ans.append(int(de**.5))
            final.append(len(ans))    
        return min(final)

def sum_of_squares(n):
        import math
        while n % 4 == 0: n = n // 4
        if n % 8 == 7: return 4
        if int(math.sqrt(n)) ** 2 == n: return 1
        i = 1
        while i*i <= n:
            j = math.sqrt(n - i*i)
            if int(j) == j: return 2
            i += 1
        return 3


#explained at: http://www.zrzahid.com/least-number-of-perfect-squares-that-sums-to-n/
def sum_of_squares(n):
    def is_sq(n): return int(n**0.5) * int(n**0.5) == n
    if is_sq(n): return 1
    while n & 3 == 0: n >>= 2
    if n & 7 == 7: return 4
    for i in range(1,int(n**0.5)):
        if is_sq(n-i*i): return 2
    return 3

def sum_of_squares(n):
    def divide_count(p):
        nonlocal n, s1, s2
        while not n % p ** 2: n //= p*p
        if not n % p:
            s1 &= False
            s2 &= p & 3 < 3
            n //= p

    s1 = s2 = True
    divide_count(2)
    s3 = n << 1-s1 & 7 < 7
    divide_count(3)
    x, wheel = 5, 2
    while x*x <= n:
        divide_count(x)
        x, wheel = x + wheel, 6 - wheel
    if n > 1: divide_count(n)
    return 4 - s3 - s2 - s1

def sum_of_squares(n):
    # three-square theorem
    if n**0.5 == int(n**0.5):
        return 1
    while n % 4 == 0:
        n >>= 2
    if (n -7) % 8 ==0:
        return 4
    for s in range(1,int(n**0.5)+1):
        if (n - s*s)**0.5 == int((n - s*s)**0.5):
            return 2
    return 3

import math

def is_perfect_sq(n):
    sr = math.sqrt(n)
    low_perfect = math.floor(sr)
    check = sr - low_perfect == 0
    #return check, low_perfect**2
    return check

def sum_of_squares(n):
    """ 
    Based on 
    1. Any number can be represented as the sum of 4 perfect squares
    2. Lagrange's Four Square theorem
    Result is 4 iff n can be written in the form 4^k*(8*m+7)
    """
    # print("Testing value of {}".format(n))
    if is_perfect_sq(n):
        return 1
    
    # Application of Lagrange theorem
    while n % 4 == 0:
        n >>= 2
    if n % 8 == 7:
        return 4
        
    # Check if 2
    for a in range(math.ceil(math.sqrt(n))):
        b = n - a * a
        if is_perfect_sq(b):
            return 2

    return 3