LeetCode #279 Perfect Squares

Medium

Problem

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Solution — Dynamic Programming

This problem is a classic dynamic programming problem that we can use previous information to construct current value by following formula:

For any integer 0 < k ≤ n, D[k] = min(1 + D[k-l²]),

where l is an integer and 0 < l < SQRT(k)

Then our answer will be at D[n].

Complexity

We will check number from 1 to n so it takes O(n) iterations. In each iteration, we will check each candidate composition and find minimum of them, which takes O(k) time if k is counts of integers that square value is less than i in this iteration. Because k will be in range 1 and i^(1/2), it takes O(i^(1/2)) time in each iteration. Therefore, totally it will take O(1^(1/2)+2^(1/2)+… +n^(1/2)) = O(n(1+n^0.5)/2) = O(n/2 + (n^1.5)/2) = O(n^1.5) time for this approach.

For space complexity, we use a distance list for saving all previous information so it will take O(n) space.

Solution — Lagrange’s Four-Square Theorem

By Lagrange’s Four-Square Theorem:

every natural number can be represented as the sum of four integer squares

and

a positive integer can be expressed as the sum of three squares if and only if it is not of the form 4^k(8m+7) for integers k and m

The result can be found quicker because it will only be less and equal to 4.

Complexity

Obviously, it will take O(k) time for finding rest number that can be divided by 4 if k denotes to the exponential number of 4 that n = 4^k*l.

Furthermore, i will be range of 0 and n^(1/2) and j will be between 0 and n-(i^2), which will be equal to i. Therefore, it will take O(k + n^(1/2)*n^(1/2)) = O(k + n) time.

It’s trivial that it only uses O(1) extra space.