Perfect Squares - Can someone explain following math?

Question

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.

Example 1:

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

Example 2:

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

Using the following knowledge about squares (given below) we can implement the following solution.

A natural number is...

1. ... a square if and only if each prime factor occurs to an even power in the number's prime factorization.
2. ... 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.
3. ... a sum of three squares if and only if it's not of the form 4a(8b+7) with integers a and b.
4. ... a sum of four squares. Period. No condition. You never need more than four.

int numSquares(int n) {
    while (n % 4 == 0)
        n /= 4;
    if (n % 8 == 7)
        return 4;
    for (int a=0; a*a<=n; ++a) {
        int b = sqrt(n - a*a);
        if (a*a + b*b == n)
            return 1 + !!a;
    }
    return 3;
}

Question:

Can someone help me understand what exactly are we trying to achieve in following for loop? I'm a little lost here.

for (int a=0; a*a<=n; ++a) {
    int b = sqrt(n - a*a);
    if (a*a + b*b == n)
        return 1 + !!a;
}

Answer 1

The loop is trying to find two squares that sum to n.

Rather than trying every combination of numbers to see if we can square them and they add up to n, we just loop through the possibilities for one of the numbers -- this is a. We square that with a*a, and subtract that from n. We then get the integer part of the square root of this difference, and this is b. If a²+b² adds up to n, this is the pair of squares that we're looking for.

We need to calculate the sum of the squares in case n - a*a wasn't a perfect square. In that case its square root will have a fraction in it, which will be lost when we convert it to an integer. In other words, testing a*a+b*b == n allows us to determine whether the square root was an integer.