# Count number of right triangles possible with a given perimeter

Given a perimeter P, the task is to find the number of right triangles possible with perimeter equal to p.

Examples:

Input: P = 12 Output: number of right triangles = 1 The only right angle possible is with sides hypotenuse = 5, perpendicular = 4 and base = 3. Input: p = 840 Output: number of right triangles = 8

So the aim is to find the number of solutions which satisfy equations a + b + c = p and a^{2} + b^{2} = c^{2}.

A **naive** approach is to run two loops for a(1 to p/2) and b(a+1 to p/3) then make c=p-a-b and increase count by one if . This will take time.

An **efficient** approach can be found by little algebraic manipulation :

Since a + c > b or, p – b > b or, b < p/2. Thus iterating b from 1 to p/2, calculating a and storing only the whole number a would give all solutions for a given p. There are no right triangles are possible for odd p as right angle triangles follow the Pythagoras theorem. Use a list of pairs to store the values of a and band return the count at the end.

Below is the implementation of the above approach.

## C++

`// C++ program to find the number of` `// right triangles with given perimeter` `#include<bits/stdc++.h>` `using` `namespace` `std;` `// Function to return the count` `int` `countTriangles(` `int` `p)` `{` ` ` `// making a list to store (a, b) pairs` ` ` `vector<pair<` `int` `,` `int` `>> store;` ` ` `// no triangle if p is odd` ` ` `if` `(p % 2 != 0)` ` ` `return` `0;` ` ` `else` ` ` `{` ` ` `int` `count = 1;` ` ` `for` `(` `int` `b = 1; b < p / 2; b++)` ` ` `{` ` ` `float` `a = (` `float` `)p / 2.0f * ((` `float` `)((` `float` `)p -` ` ` `2.0 * (` `float` `)b) /` ` ` `((` `float` `)p - (` `float` `)b));` ` ` `int` `inta = (` `int` `)(a);` ` ` `if` `(a == inta)` ` ` `{` ` ` `// make (a, b) pair in sorted order` ` ` `pair<` `int` `,` `int` `> ab;` ` ` `if` `(inta<b)` ` ` `{` ` ` `ab = {inta, b};` ` ` `}` ` ` `else` ` ` `{` ` ` `ab = {b, inta};` ` ` `}` ` ` `// check to avoid duplicates` ` ` `if` `(find(store.begin(), store.end(), ab) == store.end())` ` ` `{` ` ` `count += 1;` ` ` `// store the new pair` ` ` `store.push_back(ab);` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `count;` ` ` `}` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `p = 840;` ` ` `cout << ` `"number of right triangles = "` `<< countTriangles(p);` ` ` `return` `0;` `}` `// This code is contributed by rutvik_56.` |

## Python3

`# python program to find the number of` `# right triangles with given perimeter` `# Function to return the count` `def` `countTriangles(p):` ` ` ` ` `# making a list to store (a, b) pairs` ` ` `store ` `=` `[]` ` ` `# no triangle if p is odd` ` ` `if` `p ` `%` `2` `!` `=` `0` `: ` `return` `0` ` ` `else` `:` ` ` `count ` `=` `0` ` ` `for` `b ` `in` `range` `(` `1` `, p ` `/` `/` `2` `):` ` ` `a ` `=` `p ` `/` `2` `*` `((p ` `-` `2` `*` `b) ` `/` `(p ` `-` `b))` ` ` `inta ` `=` `int` `(a)` ` ` `if` `(a ` `=` `=` `inta ):` ` ` `# make (a, b) pair in sorted order` ` ` `ab ` `=` `tuple` `(` `sorted` `((inta, b)))` ` ` `# check to avoid duplicates` ` ` `if` `ab ` `not` `in` `store :` ` ` `count ` `+` `=` `1` ` ` `# store the new pair` ` ` `store.append(ab)` ` ` `return` `count` `# Driver Code` `p ` `=` `840` `print` `(` `"number of right triangles = "` `+` `str` `(countTriangles(p)))` |

**Output:**

number of right triangles = 8

**Time complexity:** O(P)