loading...

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

alisabaj profile image Alisa Bajramovic Updated on ・4 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

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 a2 + b2 = c.

For example, if the input were 13, the function should return true because 13 is the sum of 22 (4) and 32 (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. a2 + b2 = c is the same thing as a2 = c - b2. 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 a2 + b2 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 a2 + b2 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!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide