Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways

Today's algorithm is the Sum of Square Numbers problem:

Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a² + b² = c.

For example, if the input were 13, the function should return true because 13 is the sum of 2² (4) and 3² (9).

In this post, I'll be discussing two solutions to this problem: one that uses a for loop and checks if each value is an integer, and another that uses two pointers and checks the sum at each of those pointers. For each solution, I'll first discuss my approach, and then code them using JavaScript.

Approach #1: Using For Loops

The starting point behind this first approach is that we can rewrite the sum of squares equation in a way that's easier for us to program with. a² + b² = c is the same thing as a² = c - b². That's the same thing as a = Math.sqrt(c - b*b).

With this in mind, we want to initiate a for loop which goes from 0 to the square root of c. We can call each of those steps in the for loop b. Then, at each step of b, we'll create a variable called a, which we can set equal to the equation a = Math.sqrt(c - b*b). If a is an integer, then (since we already know b is an integer), we can return true. If, after checking each integer value of b, the equation never returned a time where a was an integer, we can return false.

Coding the Solution for Approach #1

We'll start this problem by setting up a for loop. A for loop is great for this situation because it can increment one integer at a time. So, we'll start by checking when b is 0, and go all the way up to the square root of c, since that's the largest value that b could be to satisfy the equation. We want to do Math.floor() on the square root of c because we're only interested in examining integers.

function judgeSquareSum1(c) {
  for (let b = 0; b <= Math.floor(Math.sqrt(c)); b++) {
    //...
  }
  //...
}

Inside the for loop, we can initialize a variable called a. Just like in the equation we discussed above, we'll set a equal to Math.sqrt(c - b * b).

function judgeSquareSum1(c) {
  for (let b = 0; b <= Math.floor(Math.sqrt(c)); b++) {
    const a = Math.sqrt(c - b * b);
    //...
    }
  }
  //...
}

If a is an integer, then c is the sum of two integers squared, since we know by the nature of the for loop that b is an integer. To check if it's an integer, we can do Number.isInteger(), passing in a. If it returns that it is an integer, we can return true. And, if, after checking every element in the for loop, true was never returned, we can return false.

function judgeSquareSum1(c) {
  for (let b = 0; b <= Math.floor(Math.sqrt(c)); b++) {
    const a = Math.sqrt(c - b * b);
    if (Number.isInteger(a)) {
      return true;
    }
  }
  return false;
}

Approach #2: Using Two Pointers

The second approach to this problem relies on having two pointers--one will start at 0, and the other will start at the square root of c. We'll call the pointers a and b. If a² + b² is equal to c, then we know c is the sum of squared numbers. Otherwise, we'll need to move the pointers.

If the sum of a² + b² is less than c, then we know we're checking integer values that are too small, so we should increment a. If the sum is greater than c, then we know we're checking integers that are too large, so we should decrement (or, decrease by 1) b. We'll keep doing this as long as a is less than or equal to b. If the sum was never found equal to c, then we know that c is not the sum of two integers squared.

Coding the Solution for Approach #2

In this second approach, we'll start by initializing the variables a and b. We'll set a equal to 0, and b equal to the square root of c. Just like in the first approach, however, since we're only interested in integers, we can set b equal to Math.floor(Math.sqrt(c)). This removes the possibility of b not being a whole number.

function judgeSquareSum2(c) {
  let a = 0;
  let b = Math.floor(Math.sqrt(c));
  //...
}

Now, we want to check the sum of the square of a and b as long as a is less than or equal to b. We set this as the ending point because we don't need to check the same values twice--once they meet at the same integer, we've checked all possibilities. For this approach, we can use a while loop.

Inside the while loop, we'll initialize a variable sum, setting it equal to a * a + b * b.

function judgeSquareSum2(c) {
  let a = 0;
  let b = Math.floor(Math.sqrt(c));
  while (a <= b) {
    const sum = a * a + b * b;
    //...
  }
  //...
}

If sum is equal to c, we can return true. If the sum is less than c, we can move a toward b by incrementing it. If the sum is greater than c, we can move b toward a by decrementing it.

Finally, if after checking all of the values of a and b, if at no point did sum equal c, we can return false.

function judgeSquareSum2(c) {
  let a = 0;
  let b = Math.floor(Math.sqrt(c));
  while (a <= b) {
    const sum = a * a + b * b;
    if (sum === c) {
      return true;
    } else if (sum < c) {
      a++;
    } else {
      b--;
    }
  }
  return false;
}

--

Please let me know in the comments if you have any questions or other ways of solving this problem!