> For the complete documentation index, see [llms.txt](https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-4/perfect-squares.md).
# Perfect Squares
## Problem Statement
Given a positive integer n, find the least number of perfect square numbers (for example, `1, 4, 9, 16, ...`) which sum to n.
## Testcases
```
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
```
## Prerequisite Knowledge
### Lagrange's Four-Square Theorem
#### Statement
*Every natural integer can be represented as the sum of four integer squares.*
#### Examples
### Legendre's Three-Square Theorem
This theorem could be used to [prove](https://brilliant.org/wiki/fermats-sum-of-two-squares-theorem/) Lagrange's Four-Square Theorem.
#### Statement
A natural number can be represented as the sum of three squares of integers,  if and only if the given number is *not* of the form for non-negative integers `a` and `b`.
## Algorithm
### Mathematical Approach
According to Lagrange's Four-Square Theorem, any number can be represented as the sum of four square numbers. Applying this theorem in this approach, we perform conditional checks to identify the number of perfect squares that can be used to represent the given number.
1. Check if the number itself is a perfect square and return 1 if so.
2. Check if the number can be formed using two perfect square addends.
a. Find the square root of the given number.
b. Iteratively check if the given number subtracted with a perfect square gives another perfect square i.e. the sum of two perfect squares.
c. If the conditions are satisfied, return 2.
3. Check if the number can be formed using four perfect square addends using Legendre's Three-Square Sum Theorem.
a. Check if the number is a power of 4.
b. Check if the remainder is 7 when divided by 8.
c. If the conditions are satisfied, return 4.
4. If the prior conditions are not satisfied, then the number can be formed using three perfect square addends. Return 3.
## Code
{% code title="Check Perfect Square Helper Function" %}
```cpp
int isPerfectSquare(int n) {
int sqrt_n = (int)(sqrt(n));
return (sqrt_n * sqrt_n == n);
}
```
{% endcode %}
{% code title="Sum of Perfect Squares Function" %}
```cpp
int numSquares(int n) {
// ONE ADDEND -> n = n
// The input number itself is a perfect square
if(isPerfectSquare(n)) {
return 1;
}
// TWO ADDENDS -> n = a + b
int sqrt_n = (int)(sqrt(n));
for(int i = 1; i <= sqrt_n; i++) {
if(isPerfectSquare(n - (i * i))) {
return 2;
}
}
// FOUR ADDENDS -> n = a + b + c + d
// (4 ^ k) * ((8 * m) + 7) -> Legendre's Three-Square Theorem
// Check if the number is a power of 4
while((n & 3) == 0) { // (n % 4) == 0
n >>= 2; // n /= 4;
}
// Check if the remainder is 7 when divided by 8
if((n & 7) == 7) { // (n % 8) == 7
return 4;
}
// THREE ADDENDS -> n = a + b + c
return 3;
}
```
{% endcode %}
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:
```
GET https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-4/perfect-squares.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.