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.

	#include <iostream>
	#include <math.h>
	using namespace std;
	void double_square_number(int target)
	{
	bool found = false;
	for (int i = 1; i < target/2; i++)
	{
	double squared = sqrt(i);
	int whole = (int)squared;
	if (whole == squared)
	{
	int first = whole;
	int left = target - i;
	squared = sqrt(left);
	whole = (int) squared;
	if (squared == whole)
	{
	found = true;
	cout<<target<<" = " <<first<<"^2 + "<<whole<<"^2"<<endl;
	}
	}
	}
	if (!found)
	cout<<target<<" = no two perfect spquare numbers found"<<endl;
	}
	int main()
	{
	double_square_number(10);
	double_square_number(13);
	double_square_number(17);
	double_square_number(23);
	}

view raw Double_square.cpp hosted with ❤ by GitHub

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.

	import math
	def count_ways_for_squres(N):
	result = []
	limit = int(math.sqrt(N))//2
	for i in range(1, limit + 1):
	target = N - i**2
	#target is also a squared number
	if math.sqrt(target)%1 == 0:
	result.append([i**2, target])
	return [len(result), result]
	input = 10
	print ("input = {} ways for perfect squares = {}".format(input, count_ways_for_squres(input)))
	input = 23
	print ("input = {} ways for perfect squares = {}".format(input, count_ways_for_squres(input)))

view raw facebook_find_perfect_squares.py hosted with ❤ by GitHub

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.