- 35.8%

https://leetcode.com/problems/perfect-squares/#/description

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

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Summary of 4 different solutions (BFS, DP, static DP and mathematics)

Came up with the 2 solutions of breadth-first search and dynamic programming. Also “copied” StefanPochmann’s static dynamic programming solution (https://leetcode.com/discuss/56993/static-dp-c-12-ms-python-172-ms-ruby-384-ms) and davidtan1890’s mathematical solution (https://leetcode.com/discuss/57066/4ms-c-code-solve-it-mathematically) here with minor style changes and some comments. Thank Stefan and David for posting their nice solutions!

1.Dynamic Programming: 440ms

1 | class Solution |

2.Static Dynamic Programming: 12ms

1 | class Solution |

3.Mathematical Solution: 4ms

1 | class Solution |

4.Breadth-First Search: 80ms

1 | class Solution |

https://discuss.leetcode.com/topic/23808/o-sqrt-n-in-ruby-c-c

O(sqrt(n)) in Ruby, C++, C

These solutions use some number theory (see explanation further down).

C++ solution

1 | int numSquares(int n) { |

C solution

Inspired by kevin36’s solution. We don’t really need to compute the prime factorization. Knowing that four squares always suffice and using the three-squares test is enough. Single-square and sum-of-two-squares cases can be done simpler.

1 | int numSquares(int n) { |

Explanation

I happen to have given a little talk about just this topic a while back in a number theory seminar. This problem is completely solved, in the sense of being reduced to simple checks of a number’s prime factorization. A natural number is…

- … a square if and only if each prime factor occurs to an even power in the number’s prime factorization.
- … a sum of two squares if and only if each prime factor that’s 3 modulo 4 occurs to an even power in the number’s prime factorization.
- … a sum of three squares if and only if it’s not of the form 4a(8b+7) with integers a and b.
- … a sum of four squares. Period. No condition. You never need more than four.

Of course single squares can also be identified by comparing a given number with the square of the rounded root of the number.

The problem statement says “1, 4, 9, 16, …”, for some reason apparently excluding 0, but it really is a perfect square and the above theorems do consider it one. With that, you can for example always extend a sum of two squares a2+b2 to the sum of three squares a2+b2+02. Put differently, if n isn’t a sum of three squares, then it also isn’t a sum of two squares. So you can read the above statements as “… a sum of m (or fewer) squares”. Thanks to ruben3 for asking about this in the comments.

In my above solutions, I first divide the given number by 4 as often as possible and then do the three-squares check. Dividing by 4 doesn’t affect the other checks, and the n % 8 == 7 is cheaper than the prime factorization, so this saves time in cases where we do need four squares.

Armed with just the knowledge that you never need more than four squares, it’s also easy to write O(n) solutions, e.g.:

1 | int numSquares(int n) { |

https://discuss.leetcode.com/topic/23812/static-dp-c-12-ms-python-172-ms-ruby-384-ms/2

Static DP, C++ 12 ms, Python 172 ms, Ruby 384 ms

There are so many “large” test cases that it’s worthwhile to keep data between test cases rather than recomputing from scratch all the time. At least in the slower languages. My dp tells the numbers of squares needed for the first integers, and when asked about a new n, I extend dp just as much as necessary.

C++ … 28 ms

1 | int numSquares(int n) { |

C++ … 12 ms

Switching the loops makes it less nice but faster:

1 | int numSquares(int n) { |

Python … 172 ms

1 | class Solution(object): |

There’s probably a cleaner way than using a global variable, but I’m new to Ruby and don’t know one.

https://discuss.leetcode.com/topic/26262/short-python-solution-using-bfs/2

Short Python solution using BFS

1 | def numSquares(self, n): |

The basic idea of this solution is a BSF search for shortest path, take 12 as an example, as shown below, the shortest path is 12-8-4-0:

https://discuss.leetcode.com/topic/23846/4ms-c-code-solve-it-mathematically

4ms C++ code - Solve it mathematically

1 | class Solution { |

UPDATE: in order to understand, I suggest u read:

here is the Lagrange’s Four Square theorem - Limit the result to <= 4:

https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem

And this article, in which you can also find the way to present a number as a sum of four squares:

http://www.alpertron.com.ar/4SQUARES.HTM

https://discuss.leetcode.com/topic/23906/o-sqrt-n-about-0-034-ms-and-0-018-ms/2

O(sqrt(n)), about 0.034 ms (and 0.018 ms)

For better measurement, I wrapped the actual solution in a 10000-loop. This got accepted in 344 ms (every time in three submits), so without the wrapper it should take about 0.0344 ms. I tried a few variations and this is the fastest I managed to do.

(Update: After qgambit2’s challenge, I optimized my my original approach and now that’s my fastest, with about 180 ms.)

First I use the fact that four squares always suffice and the fact that four squares are only needed for numbers of the form 4a(8b+7). After that part, I know that the answer is 1, 2 or 3, and I try to build n as sum of one or two squares.

For that, I use a kind of two-pointers-approach. Instead of going through squares a2 and checking whether n-a2 is a square (which would involve computing lots of square roots), imagine you start with a=02 and b=floor(sqrt(n))2 and as long as a<=b, either make a the next larger square or make b the next smaller square, depending on whether the sum of the two squares is too small or too large (or return 2, if it’s exactly right).

But in order to improve speed further, I use that squares are sums of consecutive odd numbers starting at 1 (for example, 25=1+3+5+7+9), and my a and b aren’t squares but the corresponding odd numbers. And instead of computing the sum of the two squares, I just add to or subtract from n, trying to reach zero. This way, my main part doesn’t even have multiplications. Just simple addition/subtraction and comparisons.

The solution:

1 | int numSquaresReal(int n) { |

The wrapper for better time measurement:

1 | int numSquares(int n) { |

488ms, 26.95%, June.15th, 2016

https://leetcode.com/discuss/62229/short-python-solution-using-bfs

1 | class Solution(object): |

Solution 2:

208ms, 60.99%, June.15th, 2016

https://leetcode.com/discuss/56993/static-dp-c-12-ms-python-172-ms-ruby-384-ms

1 | class Solution(object): |