Dado un número entero N , la tarea es encontrar el número total de triángulos en ángulo recto que se pueden formar de manera que la longitud de cualquier lado del triángulo sea como máximo N .
Un triángulo rectángulo satisface la siguiente condición: X 2 + Y 2 = Z 2 donde Z representa la longitud de la hipotenusa y X e Y representan las longitudes de los dos lados restantes.
Ejemplos:
Entrada: N = 5
Salida: 1
Explicación:
La única combinación posible de lados que forman un triángulo rectángulo es {3, 4, 5}.Entrada: N = 10
Salida: 2
Explicación:
Las posibles combinaciones de lados que forman un triángulo rectángulo son {3, 4, 5} y {6, 8, 10}.
Enfoque ingenuo: la idea es generar todas las combinaciones posibles de tripletes con números enteros del rango [1, N] y, para cada una de esas combinaciones, verificar si es un triángulo rectángulo o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to count total
// number of right angled triangle
int right_angled(int n)
{
// Initialise count with 0
int count = 0;
// Run three nested loops and
// check all combinations of sides
for (int z = 1; z <= n; z++) {
for (int y = 1; y <= z; y++) {
for (int x = 1; x <= y; x++) {
// Condition for right
// angled triangle
if ((x * x) + (y * y) == (z * z)) {
// Increment count
count++;
}
}
}
}
return count;
}
// Driver Code
int main()
{
// Given N
int n = 5;
// Function Call
cout << right_angled(n);
return 0;
}
Java
// Java implementation of
// the above approach
import java.io.*;
class GFG{
// Function to count total
// number of right angled triangle
static int right_angled(int n)
{
// Initialise count with 0
int count = 0;
// Run three nested loops and
// check all combinations of sides
for(int z = 1; z <= n; z++)
{
for(int y = 1; y <= z; y++)
{
for(int x = 1; x <= y; x++)
{
// Condition for right
// angled triangle
if ((x * x) + (y * y) == (z * z))
{
// Increment count
count++;
}
}
}
}
return count;
}
// Driver code
public static void main (String[] args)
{
// Given N
int n = 5;
// Function call
System.out.println(right_angled(n));
}
}
// This code is contributed by code_hunt
Python3
# Python implementation of # the above approach # Function to count total # number of right angled triangle def right_angled(n): # Initialise count with 0 count = 0 # Run three nested loops and # check all combinations of sides for z in range(1, n + 1): for y in range(1, z + 1): for x in range(1, y + 1): # Condition for right # angled triangle if ((x * x) + (y * y) == (z * z)): # Increment count count += 1 return count # Driver Code # Given N n = 5 # Function call print(right_angled(n)) # This code is contributed by code_hunt
C#
// C# implementation of
// the above approach
using System;
class GFG{
// Function to count total
// number of right angled triangle
static int right_angled(int n)
{
// Initialise count with 0
int count = 0;
// Run three nested loops and
// check all combinations of sides
for(int z = 1; z <= n; z++)
{
for(int y = 1; y <= z; y++)
{
for(int x = 1; x <= y; x++)
{
// Condition for right
// angled triangle
if ((x * x) + (y * y) == (z * z))
{
// Increment count
count++;
}
}
}
}
return count;
}
// Driver Code
public static void Main(string[] args)
{
// Given N
int n = 5;
// Function call
Console.Write(right_angled(n));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// javascript implementation of
// the above approach
// Function to count total
// number of right angled triangle
function right_angled(n)
{
// Initialise count with 0
var count = 0;
// Run three nested loops and
// check all combinations of sides
for(z = 1; z <= n; z++)
{
for(y = 1; y <= z; y++)
{
for(x = 1; x <= y; x++)
{
// Condition for right
// angled triangle
if ((x * x) + (y * y) == (z * z))
{
// Increment count
count++;
}
}
}
}
return count;
}
// Driver code
//Given N
var n = 5;
// Function call
document.write(right_angled(n));
// This code is contributed by Amit Katiyar
</script>
Producción:
1
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de la idea de que se puede encontrar el tercer lado del triángulo, si se conocen los dos lados de los triángulos. Siga los pasos a continuación para resolver el problema:
- Iterar hasta N y generar pares de longitud posible de dos lados y encontrar el tercer lado usando la relación x 2 + y 2 = z 2
- Si se encuentra que sqrt(x 2 +y 2 ) es un número entero, almacene los tres números enteros en cuestión en un Conjunto en orden ordenado, ya que pueden formar un triángulo rectángulo.
- Imprima el tamaño final del conjunto como el conteo requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count total
// number of right angled triangle
int right_angled(int n)
{
// Consider a set to store
// the three sides
set<pair<int, pair<int, int> > > s;
// Find possible third side
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= n; y++) {
// Condition for a right
// angled triangle
if (x * x + y * y <= n * n) {
int z = sqrt(x * x + y * y);
// Check if the third side
// is an integer
if (z * z != (x * x + y * y))
continue;
vector<int> v;
// Push the three sides
v.push_back(x);
v.push_back(y);
v.push_back(sqrt(x * x + y * y));
sort(v.begin(), v.end());
// Insert the three sides in
// the set to find unique triangles
s.insert({ v[0], { v[1], v[2] } });
}
else
break;
}
}
// return the size of set
return s.size();
}
// Driver code
int main()
{
// Given N
int n = 5;
// Function Call
cout << right_angled(n);
return 0;
}
Java
// Java implementation of the
// above approach
import java.util.*;
class Pair<F, S>
{
// First member of pair
private F first;
// Second member of pair
private S second;
public Pair(F first, S second)
{
this.first = first;
this.second = second;
}
}
class GFG{
// Function to count total
// number of right angled triangle
public static int right_angled(int n)
{
// Consider a set to store
// the three sides
Set<Pair<Integer,
Pair<Integer,
Integer>>> s = new HashSet<Pair<Integer,
Pair<Integer,
Integer>>>();
// Find possible third side
for(int x = 1; x <= n; x++)
{
for(int y = 1; y <= n; y++)
{
// Condition for a right
// angled triangle
if (x * x + y * y <= n * n)
{
int z = (int)Math.sqrt(x * x + y * y);
// Check if the third side
// is an integer
if (z * z != (x * x + y * y))
continue;
Vector<Integer> v = new Vector<Integer>();
// Push the three sides
v.add(x);
v.add(y);
v.add((int)Math.sqrt(x * x + y * y));
Collections.sort(v);
// Add the three sides in
// the set to find unique triangles
s.add(new Pair<Integer,
Pair<Integer,
Integer>>(v.get(0),
new Pair<Integer,
Integer>(v.get(1),
v.get(2))));
}
else
break;
}
}
// Return the size of set
return s.size() - 1;
}
// Driver code
public static void main(String[] args)
{
// Given N
int n = 5;
// Function call
System.out.println(right_angled(n));
}
}
// This code is contributed by grand_master
Javascript
// JavaScript implementation of the
// above approach
// Function to count total
// number of right angled triangle
function right_angled(n)
{
// Consider a set to store
// the three sides
let s = new Set();
// Find possible third side
for (let x = 1; x <= n; x++) {
for (let y = 1; y <= n; y++) {
// Condition for a right
// angled triangle
if (x * x + y * y <= n * n) {
let z = Math.floor(Math.sqrt(x * x + y * y));
// Check if the third side
// is an integer
if (z * z != (x * x + y * y))
continue;
let v = new Array();
// Push the three sides
v.push(x);
v.push(y);
v.push(Math.floor(Math.sqrt(x * x + y * y)));
v.sort();
// Insert the three sides in
// the set to find unique triangles
s.add([v[0],[v[1], v[2]]].join());
}
else
break;
}
}
// return the size of set
return s.size;
}
// Driver code
// Given N
let n = 5;
// Function Call
console.log(right_angled(n));
// The code is contributed by Gautam goel (gautamgoel962)
Producción:
1
Complejidad temporal: O(N 2 )
Espacio auxiliar: O(1)