Thread: quick question passing data types for square root function (function parameters)

This line looks wrong I suggest you verify it.

Code:

sqt = (p/temp+temp)/2;

Tim S.

C Programming/math.h/sqrt - Wikibooks, open books for an open world

Hey! I've too started solving Project Euler problems very recently and I'm regularly committing to my GitHub repository for Competitive Programming with my solutions. Project Euler is fine with people sharing solutions for the first 100 problems but I'll be making my PE folder private mostly very soon. You can find me and follow my progress here if you'd like to: Competetive-Programming-Q-A/Problems-and-Solutions/Project Euler at master * ZeusNoTZues/Competetive-Programming-Q-A * GitHub

Also, you could just use sqrt () from math.h instead of writing your own algo to do that.

Here's my solution to Problem 9. The O(N) solution is worth studying as O(N^3) and O(N^2) are naive/brute-force and easy to think about and work out. Let me know if you need any further explanation or any math proof you would like to see to understand better.

Code:

/*
Solution:

There are many ways to solve this problem. It's a very
interesting problem due to this.
There is the obvious O(N^3) approach which can be slightly
optimised. There's the O(N^2) approach that one can use given
the relations in the question between A, B, C and doing a little
math. I managed to solve the problem in these two ways but was
mind blown when I found that the problem can be solved in with
an O(N) approach by doing the math further. Thanks to my math
teacher at school and Wikipedia.

My thoughts:

-> O(N^3):
    var A, B, C : sides of the right angled triangle
    loop A [1-1000]
        loop B [1-1000]
            loop C [1-1000]
                if (A + B + C equals 1000) and
                   (A^2 + B^2 equals C^2)
                    print A, B, C

This is obviously very lazy and will take a lot of time if the upper
bound was a larger value than 1000. You can optimise this by using
the fact that A < B < C is mentioned in the question. You can optimise
this way more to make it better O(N^3) but I'll just upload the bare
minimum optimisation code as there are better ways to solve than this.
N = 1000
Upper bound for A: N/3
Upper bound for B: N/2 (and B > A)
Upper bound for C: N/2 (and C > B)

-> O(N^2)
Lets's optimise by using the facts given in the question.
(Note: ^ is not used as XOR here. It denotes "raised to the power of")

--- A + B + C = 1000
--- A + B = 1000 - C
--- A^2 + B^2 + 2 * A * B = 1000000 + C^2 - 2000 * C // Squaring both sides
--- C^2 + 2 * A * B = 1000000 + C^2 - 2000 * C       // As A^2 + B^2 = C^2
--- 2 * A * B = 1000000 - 2000 * C
--- A * B = 1000 * (500-C)
--- A * B = 1000 * (A + B - 500)
Now, the algorithm depends only upon A and B

-> O(N)
Magic!

--- A^2 + B^2 = C^2                          // Equation (1)
--- A^2 + B^2 + 2 * A * B = C^2 + 2 * A * B
--- (A + B)^2 = C^2 + 2 * A * B
--- (1000 - C)^2 - C^2 = 2 * A * B           // Equation (2)

(1) - (2):
--- A^2 + B^2 - 2 * A * B = C^2 - (1000 - C)^2 + C^2
--- (A - B)^2 = C^2 - 1000000 + 2000 * C

Now, the RHS must be a perfect square as the LHS is a perfect square.
Hence, we can loop C from N/3 (upper bound for A) to N/2 (upper bound
for B) and check if RHS is a perfect square.

Good day to you!
*/

#include <bits/stdc++.h>

using namespace std;

// O(N^3)

int main ()
{
    int Sum, A, B, C;
    cout << "A + B + C = ";
    cin >> Sum;

    for (A = 1; A < Sum; A++)
        for (B = 1; B < Sum; B++)
            for (C = 1; C < Sum; C++)
                if (A < B && B < C && A + B + C == Sum && A*A + B*B == C*C)
                    cout << A << " " << B << " " << C << endl;

    return 0;
}

// O(N^2)

int main ()
{
    int Sum, A, B;
    cout << "A + B + C = ";
    cin >> Sum;

    for (A = 1; A < Sum / 3; A++)
        for (B = 1; B < Sum / 2; B++)
            if (A < B && 2 * A * B == Sum * (Sum - 2 * (Sum - A - B)))
                cout << A << " " << B << " " << Sum - A - B << endl;

    return 0;
}

// O (N)

int main ()
{
    int Sum, C;
    cout << "A + B + C = ";
    cin >> Sum;

    for (C = Sum / 3; C < Sum / 2; C++) {
        int Value = C * C - Sum * Sum + 2 * Sum * C;
        int sqrt_val = sqrt (Value);
        bool isPerfectSquare = (sqrt_val * sqrt_val == Value);
        if (isPerfectSquare)
        {
            int A = (Sum - C + sqrt_val) / 2;
            int B = Sum - A - C;
            cout << A << " " << B << " " << C << endl;
        }
    }

    return 0;
}

interesting,what algo should be used for a ascii endless numbers calculating lots of decimals for sqrt(2) ?which is also like PI= infinite number of decimals