Sum Of Squares

Hi coders, here's our problem for today. This problem was recently asked by Facebook:

Given a number n, find the least number of squares needed to sum up to the number.

Here is an example and some starting code:

def square_sum(n):
  # Fill this in.
  print(square_sum(13))

# Min sum is 3^2 + 2^2
# 2

This looks like a complicated problem at first. But we will first look at the brute force way of solving this. That's how I went through about solving this.

What is the maximum possible sum of squares for a number n ? 
Ans: n, right. Why? Because you can represent any number n as (1*1)+(1*1)+...(1*1).

Think about some small-sized test cases now.
How about we have a function f() which does what we are trying to do. So say f(6). We can subtract (1*1) from 6, thus the remaining problem is f(5) now. Or we could have subtracted (2*2) from 6, thus the remaining problem would be f(2). This gives rise to some base cases.

If you think for a while, any positive number less than 4 can be represented only by (1*1)+(1*1)+... format. So we can say, if(n<=3), then return n.

Now the above approach is good, by will have exponential time complexity. Because we are recomputing the function f() for some numbers. In the above example of f(6) we computed f(4) twice.

Got the spark?
Does this look like overlapping subproblems? Yes! We can apply Dynamic Programming here.

Instead of recomputing the values we can maintain a DP table where we can store all the previously computed values and reuse them (classic memoization concept). Now let's look at the code for a clearer idea.

def square_sum(n):
 dp = [0] * (n+1)
 for i in range(4):
  dp[i] = i
 for i in range(4, n+1):
  dp[i] = i # max value is always by 1*1 + 1*1 + 1*1 ...
  for j in range(1, ceil(sqrt(i))+1):
   tmp = j**2
   if tmp > i:
    break
   dp[i] = min(dp[i], 1+dp[i-tmp])
 return dp[n]

Get the full code here.