Least Number of Perfect Squares that Sums to n
Given a number "n", find the least number of perfect square numbers that sum to n
For Example:
n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1)
n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)
Let's take n=12. How many ways we can find n by summing up perfect squares less than n? Note that, maximum perfect square less then n will be √n. So, we can check for each numbers in j=1 to √n whether we can break n into two parts such that one part is a perfect square j*j and the remaining part n-j*j can be broken into perfect squares in similar manner. Clearly it has a recurrence relation ps(n)=j*j+ps(n-j*j), for all possible 1≤j≤√n. We need to find such j that minimizes number of perfect squares generated.
Read full article from Least Number of Perfect Squares that Sums to n - Algorithms and Problem SolvingAlgorithms and Problem Solving
No comments:
Post a Comment