279. Perfect Squares

Problem

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= n <= 104

Problem Summary

Given a positive integer n, find several perfect squares (such as 1, 4, 9, 16, ...) such that their sum equals n. You need to minimize the number of perfect squares that make up the sum. Given an integer n, return the least number of perfect squares whose sum is n.

A perfect square is an integer whose value is equal to the square of another integer; in other words, its value is equal to the product of an integer multiplied by itself. For example, 1, 4, 9, and 16 are perfect squares, while 3 and 11 are not.

Solution Approach

• By Lagrange's four-square theorem, every natural number can be represented as the sum of the squares of four integers. The four numbers here are integers. The four-square theorem proves that any positive integer can be represented as the sum of the squares of at most four positive integers. This gives an upper bound for the answer to this problem.
• The four-square theorem can derive the three-square theorem corollary: if and only if {{< katex >}} n \neq 4^{k} \times (8m + 7){{< /katex >}}, n can be represented as the sum of the squares of at most three positive integers. Therefore, when {{< katex >}} n = 4^{k} * (8m + 7){{< /katex >}}, n can only be represented as the sum of the squares of four positive integers. At this point, we can directly return 4.
• When {{< katex >}} n \neq 4^{k} \times (8*m + 7){{< /katex >}}, we need to determine exactly how many perfect squares n can be decomposed into. The answer must be one of 1, 2, or 3. The problem asks us to find the minimum, so we check from 1 upward to see whether each case is satisfied. If the answer is 1, it means n is a perfect square, which is easy to determine. If the answer is 2, it means {{< katex >}} n = a^{2} + b^{2} {{< /katex >}}; enumerate {{< katex >}} 1 \leqslant a \leqslant \sqrt{n} {{< /katex >}}, and determine whether {{< katex >}} n - a^{2} {{< /katex >}} is a perfect square. When both 1 and 2 have been ruled out, the remaining answer can only be 3.

Code

package leetcode

import "math"

func numSquares(n int) int {
	if isPerfectSquare(n) {
		return 1
	}
	if checkAnswer4(n) {
		return 4
	}
	for i := 1; i*i <= n; i++ {
		j := n - i*i
		if isPerfectSquare(j) {
			return 2
		}
	}
	return 3
}

// Determine whether it is a perfect square
func isPerfectSquare(n int) bool {
	sq := int(math.Floor(math.Sqrt(float64(n))))
	return sq*sq == n
}

// Determine whether it can be represented as 4^k*(8m+7)
func checkAnswer4(x int) bool {
	for x%4 == 0 {
		x /= 4
	}
	return x%8 == 7
}