Double square number problem [reviewed]

Problem

Let's say there is a double square number X, which can be expressed as the sum of two perfect squares, for example, 10 is double square because 10 = 3^2 + 1^2

       Determine the number of ways which it can be written as the sum of two squares



This problem is quite similar to "two sum" problem.
Here is the algorithm:

1. Loop from 1 to X, where X is a given double square number.
    1-1: for each number i, check if it is perfect square number.
    1-2 If i is a perfect square number, subtract i from X and check if residual is also a perfect square number.
     1-3: if both are perfect square number, we found it. If not, move on to the next i.

How do we check if i is perfect square number?

We can use sqrt(x) function from C++. If the sqrt(x) (double) is the same as (int) sqrt(x), we can say x is the perfect square number.

Logging:

  20 mins: to code up the solution
  Came up with O(sqrt(N)) solution. 
  However, determining the squared number was not efficient.

Here is the code.

UPDATE(2019-07-31): resolved the problem again in python. This time the running time is slightly better since I only check the squired values that is less than sqrt(N)/2, where N is a given sum.

Practice statistics:

10:00: to write the algorithm and find the python math.sqrt() and usage of modular by 1.
10:00: to write the code.

Comments

Post a Comment

Popular posts from this blog

Planting flowers with no adjacent flower plots

Find the maximum number of bomb that can be detonated