Which triplets to display?

#1

For example for input as 5,there are two possible triplets,3,4,5 and 5,12,13. The program I have written will display the smaller numbers of the triplet if the largest is entered,but will display the larger ones if the smallest is entered.

So if I enter 5,it will give 3,4 as output and if I give 3,it will give 4,5 as output. The conflict comes with 5 though.Entering 5 will only give 3,4 and not 12,13. Since 5 sits with the first condition my program will skip 12,13.I can modify it by I want to know do I have to display both these sets of triplets for 5.

#2

hello @Nitin-Bhattacharyya-2319140631658033

yeah this could create an issue.
follow this approach to generate what the want in test cases
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. 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.
#3

so basically if the input is 5,the desired triplet should be 12,13 and if the input is 12 the desired output should be 35,37?

#4

as per above formula if u r getting this then yes output should be like this only.

#5


This is the one which I did according to your suggestion,but it didnt pass the test cases(some not all)


This is the one I thought up earlier,but this will give runtime exceeded error since I couldnt think up properly how to print -1 in case there is no triplet. Can you see both these programs and if possible correct the code in the second linl?

#6

@Nitin-Bhattacharyya-2319140631658033
check ur updated code here->

for n < 3 there is no triplet possible for other cases it always exists .

in ur second case u r iterating 10^9 ,which will give tle

#7

Can you explain this part a bit?I am slightly confused how this condition/loop is working
while(cin>>n){

    if(n<3){

    cout<<"-1\n";

       continue;

    }
#8

actually there r multiple inputs , thats why i m using while loop.
while(cin>>n) this loop stops when no input is left

#9

oh ok.Thanks for bearing with my doubts and resolving them so clearly.Really grateful

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.