Your answer is one click away!

yanis February 2016
### Algorithm for finding the smallest number of precise squares which amount is n

I am supposed to write a function with one argument `n`

and the function should count the smallest number of precise squares which amount is `n`

. For example if n=10, the function should return 2 (10=3^{2} +1^{2}). So far i have implemented some solution- using dynamic programming but I am not absolutely sure of its correctness:

```
Squares(n)
dyn[0...n]
dyn[0] <- 0
for k <- 1 to n
dyn[k] <- k+1
i <- 1
j <- 1
while j<=k do
if dyn[k-j] < dyn[k]
dyn[k] <- dyn[k-j]
i <- i+1
j <- i*i
dyn[k] <- dyn[k]+1
k <- n
return dyn[n]
```

Please, analyze my solution and if you can provide faster one? So far its running time is O(n^{3/2}).

You do not need any of this. You have to know some math stuff.

- Some numbers are already squares
`int(sqrt(x))**2 == x`

- Some numbers can be represented as sum of 2 squares (Fermat)
- Some numbers can be represented as sum of 3 squares (Legendre)
Every number can be represented as sum of 4 squares (Lagrange)

So just check first two conditions and if non of them holds - return 4.

Asked in February 2016

Viewed 1,545 times

Voted 7

Answered 1 times

Viewed 1,545 times

Voted 7

Answered 1 times