Press "Enter" to skip to content

Find Whether a Number Can Be the Sum of Two Squares

Ajk 0

Today we are going to take a look at slightly mathematical problem: Find Whether a Number Can Be the Sum of Two Squares.

Being asked this question, our first step, as always, should be to clear out assumptions. As I’ve mentioned in my Find Two Primes Whose Sum is Equal K post, usually problems that are more mathematical, have easier to understand assumptions.

  • Do we need to find such numbers, or just detect wether such numbers exist? For now let’s assume we only need to return whether such numbers exist and not necessarily find the numbers.
  • Will we accept one of the numbers being 0? So would something like 02 + K2 = N2 be considered a valid solution? For now let us assume having a 0 in the sum would be a valid solution.

Once we got our simple assumptions out of the way, let us dive in to thinking about some brute force approach. The simplest thing would be to just check every number and every possible square.

Find Whether a Number Can Be the Sum of Two Squares – Brute Force Algorithm

  • For each number i from 0 to square root of N.
  • For each number j from 0 to square root of N.
  • Check if i2 + j2 is equal to N.

Note that we included a slight optimization, which is to only look at numbers less than the square root of N, since at least one of the two numbers we are trying to find out should be less than that, for their square’s sums to be equal to N.

Now let us do a quick pass to a small code sample to produce the solution discussed above.

Find Whether a Number Can Be the Sum of Two Squares – Brute Force Solution

Note that we are using long to prevent integers from overflowing. The analysis of this method should be pretty easy since it just does a double loop over ?N, so Time Complexity is O(N) and Space Complexity is O(1).

Now that we got over the brute force part, let us try to optimize the solution. Most mathematical problems’ optimizations lie in the mathematical problem itself. So let’s see if we can cut out one of the loops. After all, once we have one number, it should be relatively easy to see if the equation can be true.

Find Whether a Number Can Be the Sum of Two Squares – Optimized Algorithm

  • For each number i from 0 to square root of N.
  • Check if N – i2 is the square of some number.

Find Whether a Number Can Be the Sum of Two Squares – Optimized Solution

The analysis of this method should also be pretty easy since it just does a loop over ?N, so Time Complexity is O(?N) and Space Complexity is O(1).

There are some more advanced techniques to deal with this problem that involve Fermat’s Theorem, but you do not need to know these, since it does not overly optimize the solutions proposed here.

The solutions we wrote to find whether a number can be the sum of two squares, did seem straight forward, but be attentive in making sure you are able to solve them in little time.

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂