CODEWITHSUNDEEP
c
Thatdude1
Thatdude1

Reputation: 903

Sum of two squares in C

I have managed to get the sum of two squares, but it still doesnt work if for example 10: i need 9 and 1 ... My idea is to seacrch all the previous squares and find out how many will add up to the input, (max = 4) ... but im get stuck when duplicates occur and when i need to add 3 things... For 4 things I'm thinking of just adding an else statement. Any ideas/suggestions of how i can improve my algorithm?

Upvotes: 7

Views: 1886

Answers (1)

asaelr
asaelr

Reputation: 5456

Assume that you aren't supposed to use complex algorithm, I suggest you to loop through all the options, and check if the sum of squares make the number you need. While computing, you may also want to save the numbers in a global array, to simplify getsquare

Edit: since it's a nice problem, I wrote some code. (WARNING: I didn't check it)

int root[4];

int isqrt(int i) {return (int)floor(sqrt((double)i));}

// check if n is sum of s squares. assume s<=4
int canbesum(int s,int n) {
    if (s==0) return n==0;
    int i;
    for (i=isqrt(n);i;i--)
        if (canbesum(s-1,n-i*i)) {
            root[s-1]=i;
            return 1;
        }
    return 0;
}

int sumofsquares (int x) {
    int i;
    for (i=0;i<=4;i++) if (canbesum(i,x)) return i;
}

Upvotes: 2

Related Questions