2
\$\begingroup\$

I have been trying to solve this problem, and after a bit of googling, I realised a \$O(\sqrt{n})\$ time complexity works fine (though the algorithm suggested is different from that I have used). My algorithm is as follows (pseudo code):

for i in range(sqrt(n/2+1)):
    if n-i*i is a perfect square:
        return True
return False

The exact code is as follows:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX 100000000
typedef unsigned long long int llu;
int isSquare(llu n){
    if(n%16!=0 && n%16!=1 && n%16!=9 && n%16!=4)
        return 0;//as a square can only be of the form 16n+r ,where r belongsto {0,1,4,9}
    //The above step prevents use of expensive function sqrtl() in 75% cases
    llu root = sqrtl(n);
    return root*root == n;
}
int isSqSum(llu n){
    if(n%4==3)//as sum of two squares cannot be of the form 4n+3
        return 0;
    llu i;
    for(i=0;i*i<n/2+1;++i)
        if(isSquare(n-i*i)) 
            return 1;
    return 0;
}
int main()
{
    int c ;
    scanf("%d",&c);
    llu n;
    while(c--){
        scanf("%llu",&n);
        if(isSqSum(n))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
} 

As you can see, I have already applied most of the optimizations I could think of, but I still keep getting TLE. Is there something wrong with my code or is it that the algorithm that I am using has a large constant of proportionality in time complexity?

\$\endgroup\$
3
  • 2
    \$\begingroup\$ For a bruteforcing, I'd recommend to set up a table of perfect squares. It is not that large: MAX is 10^8, so you only need 10^4 entries. \$\endgroup\$
    – vnp
    May 29, 2014 at 18:05
  • \$\begingroup\$ You can find a different way to do so (using arithmetic). I am not sure how much faster it will be. \$\endgroup\$
    – SylvainD
    Jun 3, 2014 at 12:37
  • \$\begingroup\$ Consider putting "this method" in your post. Such external links may go leaving your post not understandable. \$\endgroup\$ Jun 7, 2014 at 4:44

2 Answers 2

1
\$\begingroup\$
  1. llu root = sqrtl(n); is not safe. The precision of a long double is not specified by C to give the exact correct answer for all unsigned long long.

  2. Not sure yet why you get TLE (Time Limit Exceeded). As the page you point to only has 10 small integers to test, there must be horribly wrong with your compilation or yu have an unstated interesting input.

  3. Spent 30 minutes tracking down a bug because I forgot to a braces when extending the following. Instead, highly reccomend to add breaces in all for(), if(), etc. except maybe in the the most trivial circumstance.

    for(i=0;i*i<n/2+1;++i)
      if(isSquare(n-i*i)) 
        return 1;
    
    // Better
    for(i=0;i*i<n/2+1;++i) {
      if(isSquare(n-i*i)) {
        return 1;
      }
    }
    
\$\endgroup\$
0
\$\begingroup\$

You can improve your algorithm by using sqrt only once.

You are looking for (i,j) such that i^2 + j^2 == n with i<j. You are iterating over all i=0,...,[sqrt(n)]. Notice that when incrementing i, the corresponding j would decrement. Moreover since i<j if you increment i by one, the corresponding j cannot decrease more than 1.

So if you keep track of the minimum j such that i*i + j*j >=n when you increment i you only have to check between j and j-1 as the new value for j. The check involves the computation of two square, no sqrt is required.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.