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 a2 + b2 = c2.
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 Codeint main(){ int p = 840; cout << "number of right triangles = " << countTriangles(p); return 0;}// This code is contributed by rutvik_56. |
Java
// Java code for implementationimport java.util.*;class Pair { int first, second; public Pair(int first, int second) { this.first = first; this.second = second; } } class GFG { // Function to return the count value static int countTriangles(int p) { // creating a list to store (a, b) pairs HashSet<Pair> store = new HashSet<Pair>(); // no triangle if p is odd if (p % 2 != 0) return 0; else { int count = 1; for(int b = 1; b < p / 3; 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 ab; if(inta<b) { ab = new Pair(inta, b); } else { ab = new Pair(b, inta); } // check to avoid duplicates if(!store.contains(ab) ) { count += 1; // store the new pair store.add(ab); } } } return count; } } // Drive Code public static void main(String[] args) { int p = 840; System.out.print("number of right triangles = " + countTriangles(p)); }} |
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 Codep = 840print("number of right triangles = "+str(countTriangles(p))) |
C#
// C# program to find the number of// right triangles with given perimeterusing System;using System.Collections.Generic;public class GFG { public class pair { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to return the count static int countTriangles(int p) { // making a list to store (a, b) pairs HashSet<pair> store = new HashSet<pair>(); // no triangle if p is odd if (p % 2 != 0) return 0; else { int count = 1; for (int b = 1; b < p / 3; b++) { float a = (float) p / 3 * ((float) ((float) p - 2 * (float) b) / ((float) p - (float) b)); int inta = (int) (a); if (a == inta) { // make (a, b) pair in sorted order pair ab; if (inta < b) { ab = new pair(inta, b); } else { ab = new pair(b, inta); } // check to astatic void duplicates if (!store.Contains(ab)) { count += 1; // store the new pair store.Add(ab); } } } return count; } } // Driver Code public static void Main(String[] args) { int p = 840; Console.Write("number of right triangles = " + countTriangles(p)); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program to find the number of// right triangles with given perimeter class pair { constructor(first , second) { this.first = first; this.second = second; } } // Function to return the count function countTriangles(p) { // making a list to store (a, b) pairs var store = new Set(); // no triangle if p is odd if (p % 2 != 0) return 0; else { var count = 1; for (var b = 1; b < p / 3; b++) { var a = p / 3 * ( ( p - 2 * b) / ( p - b)); var inta = parseInt( a); if (a == inta) { // make (a, b) pair in sorted order var ab; if (inta < b) { ab = new pair(inta, b); } else { ab = new pair(b, inta); } // check to afunction duplicates if (!store.has(ab)) { count += 1; // store the new pair store.add(ab); } } } return count; } } // Driver Code var p = 840; document.write("number of right triangles = " + countTriangles(p));// This code is contributed by Rajput-Ji </script> |
Output:
number of right triangles = 8
Time complexity: O(P)
Space complexity: O(n) as auxiliary space is being used
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
