0

so I was recently trying out a question and wrote some code but I couldn't manage to pass more than 3 test cases out of 5. the ques is: Given a number N (denoting one of the legs of the triangle), Print its Pythagoras pair in increasing order if they exist. Otherwise, print "-1".

Input Format A single integer N

Constraints N <= 10^9

Output Format Two numbers X and Y denoting the rest of the numbers of the Pythagorean triplet in increasing order.

Sample Input 3 Sample Output 4 5

My Solution:

   #include<iostream>
    #include<cmath>
    using namespace std;
    int main() {    
        int n;
        cin>>n;
        if(n>=0 && n<=2){
            cout<<"-1"<<endl;
            }
        else if (n%2==0){
            cout<<pow((n/2),2)-1<<" "<<pow((n/2),2)+1<<endl;
        }
        else if (n%2==1){
            cout<< 2*((n-1)/2)*((n+1)/2) <<" "<<pow((n+1)/2,2) + pow((n-1)/2,2)<<endl;
        }

        else{
            cout<<"-1"<<endl;
        }
        return 0;
    }

can someone suggest what am i missing in this ?

prateek nanda
  • 3
  • 1
  • 2
  • 9
  • 1
    A Pythagorean triplet consists of integers. `pow` produces a floating point number. A good first step would be writing an integer-squaring function. – molbdnilo Jun 01 '20 at 11:07
  • ... and if you use a set of known triplets, you should be able to find where it breaks down. You can use [this](https://godbolt.org/z/_-WEwV) to start testing. – Ted Lyngmo Jun 01 '20 at 11:12
  • 2
    final `else` is never reached... – Jarod42 Jun 01 '20 at 11:15

2 Answers2

1

There are some issues you could address.

  • The chained ifs should be modified (as noted in the comments, the last cout<<"-1"<<endl; is never reached) and could be simplified (if a number is not even, it's odd).

  • The code reads int values, but the constraints state that the number could be as big as 109. A long int is guaranteed to be able to store such value.

  • To square the values, a call to std::pow(..., 2); is used. Since C++11, if any argument has integral type, it is cast to double and the return value is also of type double. This may introduce rounding errors that an integral calculation (with an integral type having a big enough size) wouldn't have. Note that, given the constraints, (0.5 * 109)2 = 2.5 * 1017 which is bigger than 253 + 1 (~9 * 1015), the first integer number not exactly representable by an IEE 754 double.

  • The posted algorithm finds a triple, but a number may appear in many of them. E.g. given 20 as input, the posted code outputs

    99 101

    Other possible triples beeing (20, 21, 29) or (20, 15, 25).

That said, a possible implementation could be the following

#include <iostream>

long long int square(long int x)
{
    return static_cast<long long int>(x) * x;
}

int main()
{    
    long int n;
    while (std::cin >> n) {
        if( n <= 2 ) {
            std::cout << "-1\n";
        }
        else {
            if ( n % 2 == 0 ) {
                long long int q = square(n / 2);
                std::cout << (q - 1) << " " << (q + 1) << '\n';
            }
            else {
                long long int q = square(n);
                std::cout << (q - 1)/2 << " " << (q + 1)/2 << '\n';
            }
        }
    }
}
Bob__
  • 12,361
  • 3
  • 28
  • 42
1

The legs of a right triangle are the two sides that intersect to determine the right angle. The remaining side is called the hypotenuse. So we have to print one remaining leg other than the input and the hypotenuse.

Solution Approach:

If m>n>0 are integers, then (m2-n2, 2mn, m2+n2) is a Pythagorean triple. This is easily seen with a bit of algebra. Thus, plugging in various (m,n) will give various triples. Now, our goal is to find a triple of the form (m2-n2, 2mn, m2+n2) in which our input value is one of the catheti(legs). Note that the catheti are m2-n2 and 2mn. Also, note that the second cathetus is always even. Thus, it makes sense to consider two cases:

If a is even, then let’s try to equate it with the second cathetus, 2mn, i.e., let’s try to find an (m,n) pair such that 2mn = a. In this case, is even, so we can divide by 2. We have mn = a/2. Thus, all we have to do is to find a factorization of a/2 into mn such that m>n. You can try various factoring methods — even naïve O(√a) time method will pass - but in this case , we don’t really even need to do that, since the trivial (m,n) = (a/2,1) works!. This gives us the solution triple ( (a^2)/4 - 1, a, (a^2)/4 + 1 ). Note that (a^2)/4 is an integer since a is even.

If a is odd, then we can’t equate it with the second cathetus, so let’s try instead m2-n2, i.e. we want to find an (m,n) such that m2-n2 = a. Node that m2-n2 = (m+n)(m-n), so all boils down again to factoring! Let’s try our trivial factorization again: (m+n, m-n) = (a,1) What we get is a system of two linear equations: m+n=a and m-n=1 which has solution m=(a+1)/2 and n=(a-1)/2. Substituting back, this gives us the triple (a, (a^2 - 1)/2, (a^2 + 1)/2). Note that (a^2 + 1)/2 is an integer as a is odd.

int main()
{
  long long n;
  cin>>n;
  if (n<=2)
    cout<<"-1";
  else if (n % 2 == 0)
  {
    // Calculating for even case
    long long var = 1 * n * n / 4;
    cout<<var - 1<<" ";
    cout<<var + 1;
  }
  else if (n % 2 != 0)
  {
    //Calculating for odd case
    long long var = 1 * n * n + 1;
    cout<<var / 2 - 1<<" ";
    cout<<var / 2;
  }
return 0;
}
msepai
  • 11
  • 1