Count number of right triangles possible with a given perimeter

0 0 5 minutes read

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² + b² = c².
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 $a*a + b*b == c*c$ . This will take $O(p^{2})$ time.
An efficient approach can be found by little algebraic manipulation :

$a^{2}+b^{2}=c^{2} or, (a+b)^{2}-2ab = c^{2} or, (p-c)^{2}-2ab = c^{2} or, p^{2}-2cp-2ab = 0 or, 2ab = p^{2}-2cp or, 2ab = p^{2}-2p(p-a-b) or, 2a(p-b) = p(p-2b) or, a = (p/2) * ((p-2b)/(p-b))$

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.

Java

// Java code for implementation
import 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 Code
p = 840
print("number of right triangles = "+str(countTriangles(p)))

C#

// C# program to find the number of
// right triangles with given perimeter
using 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 zambiatek!