Sum of Square Numbers 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 &gt;= 0; i--) {
      for(let y = 0; y &lt;= 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?
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 &gt;= 0; i--) {
        for(let y = 0; y &lt;= 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 &lt;= 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 &lt;= 2) {
        return true
    }
    // Remove even factors:
    while (c % 2 === 0) {
        c /= 2;
    }
    // Find odd prime factors:
    for (let p = 3; p &lt;= 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 &amp;&amp; e % 2 === 1) {
                return false;
            }
        }
    }
    // If c &gt; 1 at this point then it is another prime factor:
    if (c % 4 === 3) {
        return false;
    }
    return true;
};