This is the sixth day of my participation in the More text Challenge. For details, see more text Challenge

Sum of squares (Question Number 633)

The title

Given a non-negative integer C, you want to determine whether there are two integers a and b such that a2 + b2 = c.

Example 1:

Input: c = 5 Output: true Description: 1 * 1 + 2 * 2 = 5Copy the code

Example 2:

Input: c = 3 Output: falseCopy the code

Example 3:

Input: c = 4 Output: trueCopy the code

Example 4:

Input: c = 2 Output: trueCopy the code

Example 5:

Input: c = 1 Output: trueCopy the code

Tip:

  • 0 <= c <= 231 - 1

link

Leetcode-cn.com/problems/su…

explain

This one, this one looks like a double pointer.

Because there’s no better way to determine the values of a and b, you just have to look for them little by little, and that would be a double pointer.

The left boundary is easy to determine — 0, and the right boundary is easy to determine, just by taking the square root of the number.

The rest is the classic double-pointer operation, which I won’t go into here.

Your own answer (double pointer)

var judgeSquareSum = function(c) {
  var left = 0
      right = ~~Math.sqrt(c)
  while (left <= right) {
    var res = Math.pow(left, 2) + Math.pow(right, 2)
    if (res === c) return true
    if (res < c) {
      left++
    } else {
      right--
    }
  }
  return false
};
Copy the code

Right? It’s easy to see the answer, nothing to say, but some people are confused about whether the double pointer will miss the correct answer, but I don’t know why.

The author is more concerned about the performance of another method 👇 :

Another way (loop)

Take a look at the code 👇 :

var judgeSquareSum = function(c) {
  for (let a = 0; a * a <= c; a++) {
    const b = Math.sqrt(c - a * a);
    if (b === parseInt(b)) {
      return true;
    }
  }
  return false;
};
Copy the code

To be honest, at first glance I can’t see much of a problem with this code, and even feel that it performs better than double Pointers. But I was wrong, both execution time and memory footprint are much higher than double pointer, why?

First, look at the number of executions. The author has carried out statistics on both the inside of the while and for loops, and found that the inside of the while loop was executed 17 times, and the for loop was executed only 16 times, which is even better. But what makes them so different is actually a closer comparison.

First of all, I’ll probably get rid of some of the calculations that are similar, so I can get rid of the loop of one time difference, because the internal logic of both is relatively simple.

Next, look at the code for a * a and math.pow (). Both are similar and are executed twice during the loop, which is also erased here.

Further down are some if… Else and assignment to variables, because they’re not that far apart, so I’m going to get rid of that, so what’s left is math.sqrt (), and that’s the point.

In a double pointer, we only take the square root of c at the beginning of the function, which is not true inside the while, but in the loop, math.sqrt () is called once each time, which is the root of the loop.

Math.sqrt() is executed 15 more times.

A Better Way (mathematics)

All right, so we’re super dimensional here, and we have no idea what we’re talking about, and the answer is we have to do prime factorization first, and then determine whether all the powers of the prime factors like 4K plus 34 times k times plus 3 are even.

Here’s the code:

var judgeSquareSum = function(c) { for (let base = 2; base * base <= c; Base++) {// enumerate the next if (c % base! == 0) { continue; } // Calculate the power of base. Let exp = 0; while (c % base == 0) { c /= base; exp++; } if (base % 4 === 3 && exp % 2! == 0) { return false; } // Return c % 4!;} // Return c % 4!; = = 3; };Copy the code

Those who want specific understanding can see official answer, here, official return even “careful” ground pasted proof process address…




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ