Sum of Square Numbers

Question

I was trying to solve a task on leetcode, where I need to find if a positive integer is the sum of squares of two other integers. My solution is below, but it fails due to exceeding time limit.

var judgeSquareSum = function(c) {
 let output = false;
 for(let i = c; i >= 0; i--) {
 for(let y = 0; y <= i; y++) {
 let sum = i*i + y*y;
 if (sum == c) 
 output = true;
 }
 }
 return output;
};

How can I make this so that is efficient, and without two iterations?

• CiaPan: Try to reduce the amount of computation, e.g. with the formula for a sum of n natural numbers trans4mind.com/personal_development/mathematics/series/…
• Blindman67: Does 0 count as a integer, eg 0 * 0 + 0 * 0 === 0 or 0 * 0 + 3 * 3 === 9 ?
• Leff: Apparently, it does.
• Blindman67: Well then the very first test is if(Math.sqrt(c) % 1 === 0) {return true} will eliminate many iterations. Also a good number to start searching down from would be Math.floor(Math.sqrt(c)) as it cant be greater than that.
• Martin R: What about some mathematics? "An integer greater than one can be written as a sum of two squares if and only if its prime decomposition contains no prime congruent to 3 (mod 4) raised to an odd power"

Answer 1

You restrict the scope of the variables to the nearest enclosing scope with let, which is good.

The use of whitespace is not consistent: for( vs if (.

The variable names seem a be arbitrary: Why i and y, and not a and b as in the LeetCode problem description?

The first you can do to speed things up is to "early return":

var judgeSquareSum = function(c) {
 for(let i = c; i >= 0; i--) {
 for(let y = 0; y <= i; y++) {
 let sum = i*i + y*y;
 if (sum == c) 
 return true;
 }
 }
 return false;
};

There is no need to continue with the loops if a decomposition into a sum of two squares has been found.

Now note that one integer in the decomposition determines the other. If we have a test candidate \$ a \$ for \$ c = a^2 + b^2 \$ then it suffices to check if \$ \sqrt{c - a^2} \$ is an integer. Also we can assume that \$ a \le b \,ドル which restricts the range of \$ a \$:

var judgeSquareSum = function(c) {
 let aMax = Math.sqrt(c/2);
 for (let a = 0; a <= aMax; a++) {
 let b = Math.sqrt(c - a * a);
 if (b === Math.round(b)) {
 return true;
 }
 }
 return false;
};

Only one loop instead of two nested loops now!

Further improvement is possible with the help of mathematics. As stated in Sum of two squares theorem,

An integer greater than one can be written as a sum of two squares if and only if its prime decomposition contains no prime congruent to 3 (mod 4) raised to an odd power.

So we need to determine if in the prime factorization $$ c = p_1^{e_1} p_2^{e_2} \cdots p_n^{e_n} $$ there is a term \$ p_j^{e_j} \$ such that \$ p_i = 3 \bmod 4 \$ and \$ e_j \$ is odd.

This is more code, but very efficient for for large numbers, because

• the range of prime candidates \$ p \$ can be bounded by \$ \sqrt c \,ドル and
• once a prime factor is found, \$ c \$ can be divided by that factor, thus reducing the remaining number of iterations.

Here is a possible implementation, with more explaining comments inline:

var judgeSquareSum = function(c) {
 // Handle 0, 1, and 2 directly:
 if (c <= 2) {
 return true
 }
 // Remove even factors:
 while (c % 2 === 0) {
 c /= 2;
 }
 // Find odd prime factors:
 for (let p = 3; p <= Math.sqrt(c); p += 2) {
 if (c % p === 0) {
 // Determine exponent e of p in c:
 let e = 0;
 while (c % p === 0) {
 e += 1;
 c /= p; // Remove this prime factor
 }
 // Is it a prime congruent 4 (mod 3), raised to an odd power?
 if (p % 4 === 3 && e % 2 === 1) {
 return false;
 }
 }
 }
 // If c > 1 at this point then it is another prime factor:
 if (c % 4 === 3) {
 return false;
 }
 return true;
};

• Marc Rohloff: A small change I would add is pre-calculating Math.sqrt(c/2) rather than calculating it on every iteration.
• Martin R: @MarcRohloff: You are right, thanks. (The final version intentionally re-calculates the bound because c becomes smaller during the iteration.)
• le_m: Some optional untested 32-bit micro-optimizations to reduce the number of slow division operations: p % 2 → p & 1, p % 4 → p & 3, c % p followed by c /= p → might be able to get rid of the modulo by dividing first and checking the result for isInteger