Dada una array de enteros, necesitamos averiguar si es posible construir al menos un triángulo no degenerado utilizando valores de array como sus lados. En otras palabras, necesitamos encontrar 3 índices de array de este tipo que puedan convertirse en lados de un triángulo no degenerado.
Ejemplos:
Input : [4, 1, 2] Output : No No triangle is possible from given array values Input : [5, 4, 3, 1, 2] Output : Yes Sides of possible triangle are 2 3 4
Para un triángulo no degenerado, sus lados deben seguir estas restricciones,
A + B > C and B + C > A and C + A > B where A, B and C are length of sides of the triangle.
La tarea es encontrar cualquier triplete de la array que satisfaga la condición anterior.
Una solución simple es generar todos los tripletes y, para cada triplete, verificar si forma un triángulo o no al verificar las tres condiciones anteriores.
Una solución eficiente es la clasificación por uso. Primero, ordenamos la array, luego hacemos un bucle una vez y verificaremos tres elementos consecutivos de esta array si algún triplete satisface arr[i] + arr[i+1] > arr[i+2], luego mostraremos ese triplete como nuestro resultado final.
¿Por qué verificar solo 3 elementos consecutivos funcionará en lugar de probar todos los tripletes posibles de una array ordenada?
Supongamos que estamos en el índice i y 3 segmentos de línea son arr[i], arr[i + 1] y arr[i + 2] con relación arr[i] < arr[i+1] < arr[i+2], Si no pueden formar un triángulo no degenerado, segmentos de línea de longitudes arr[i-1], arr[i+1] y arr[i+2] o arr[i], arr[i+1] y arr [i+3] no puede formar un triángulo no degenerado porque la suma de arr[i-1] y arr[i+1] será incluso menor que la suma de arr[i] y arr[i+1] en primer caso y la suma de arr[i] y arr[i+1] debe ser menor que arr[i+3] en el segundo caso, así que no necesitamos probar todas las combinaciones, probaremos solo 3 índices consecutivos de array en forma ordenada.
La complejidad total de la siguiente solución es O(n log n)
Implementación:
C++
// C++ program to find if it is possible to form a triangle
// from array values
#include <bits/stdc++.h>
using namespace std;
// Method prints possible triangle when array values are
// taken as sides
bool isPossibleTriangle(int arr[], int N)
{
// If number of elements are less than 3, then no
// triangle is possible
if (N < 3)
return false;
// first sort the array
sort(arr, arr + N);
// loop for all 3 consecutive triplets
for (int i = 0; i < N - 2; i++)
// If triplet satisfies triangle condition, break
if (arr[i] + arr[i + 1] > arr[i + 2])
return true;
return false;
}
// Driver Code
int main()
{
int arr[] = { 5, 4, 3, 1, 2 };
int N = sizeof(arr) / sizeof(int);
isPossibleTriangle(arr, N) ? cout << "Yes" : cout << "No";
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to find if it is possible to form a triangle
// from array values
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
// Method prints possible triangle when array values are
// taken as sides
bool isPossibleTriangle(int arr[], int N)
{
// If number of elements are less than 3, then no
// triangle is possible
if (N < 3)
return false;
// first sort the array
qsort(arr, N, sizeof(int), cmpfunc);
// loop for all 3 consecutive triplets
for (int i = 0; i < N - 2; i++)
// If triplet satisfies triangle condition, break
if (arr[i] + arr[i + 1] > arr[i + 2])
return true;
return false;
}
// Driver Code
int main()
{
int arr[] = { 5, 4, 3, 1, 2 };
int N = sizeof(arr) / sizeof(int);
isPossibleTriangle(arr, N) ? printf("Yes") : printf("No");
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
JAVA
// Java program to find if it is possible to form a
// triangle from array values
import java.io.*;
import java.util.Arrays;
class GFG {
// Method prints possible triangle when array values are
// taken as sides
static boolean isPossibleTriangle(int[] arr, int N)
{
// If number of elements are less than 3, then no
// triangle is possible
if (N < 3)
return false;
// first sort the array
Arrays.sort(arr);
// loop for all 3 consecutive triplets
for (int i = 0; i < N - 2; i++)
// If triplet satisfies triangle condition, break
if (arr[i] + arr[i + 1] > arr[i + 2])
return true;
return false;
}
// Driver Code
static public void main(String[] args)
{
int[] arr = { 5, 4, 3, 1, 2 };
int N = arr.length;
if (isPossibleTriangle(arr, N))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python
# Python3 code to find if
# it is possible to form a
# triangle from array values
# Method prints possible
# triangle when array
# values are taken as sides
def isPossibleTriangle (arr , N):
# If number of elements
# are less than 3, then
# no triangle is possible
if N < 3:
return False
# first sort the array
arr.sort()
# loop for all 3
# consecutive triplets
for i in range(N - 2):
# If triplet satisfies triangle
# condition, break
if arr[i] + arr[i + 1] > arr[i + 2]:
return True
# Driver Code
arr = [5, 4, 3, 1, 2]
N = len(arr)
print("Yes" if isPossibleTriangle(arr, N) else "No")
# This code is contributed
# by "Sharad_Bhardwaj".
C#
// C# program to find if
// it is possible to form
// a triangle from array values
using System;
class GFG
{
// Method prints possible
// triangle when array values
// are taken as sides
static bool isPossibleTriangle(int []arr,
int N)
{
// If number of elements
// are less than 3, then
// no triangle is possible
if (N < 3)
return false;
// first sort the array
Array.Sort(arr);
// loop for all 3
// consecutive triplets
for (int i = 0; i < N - 2; i++)
// If triplet satisfies triangle
// condition, break
if (arr[i] + arr[i + 1] > arr[i + 2])
return true;
return false;
}
// Driver Code
static public void Main ()
{
int []arr = {5, 4, 3, 1, 2};
int N = arr.Length;
if(isPossibleTriangle(arr, N))
Console.WriteLine("Yes" );
else
Console.WriteLine("No");
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find if
// it is possible to form
// a triangle from array values
// Method prints possible
// triangle when array values
// are taken as sides
function isPossibleTriangle( $arr, $N)
{
// If number of elements are
// less than 3, then no
// triangle is possible
if ($N < 3)
return false;
// first sort the array
sort($arr);
// loop for all 3
// consecutive triplets
for ( $i = 0; $i < $N - 2; $i++)
// If triplet satisfies triangle
// condition, break
if ($arr[$i] + $arr[$i + 1] > $arr[$i + 2])
return true;
}
// Driver Code
$arr = array(5, 4, 3, 1, 2);
$N = count($arr);
if(isPossibleTriangle($arr,$N))
echo "Yes" ;
else
echo "No";
// This code is contributed by vt_m
?>
Javascript
<script>
// Javascript program to find if it is
// possible to form a triangle
// from array values
// Method prints possible
// triangle when array values
// are taken as sides
function isPossibleTriangle(arr, N)
{
// If number of elements are
// less than 3, then no
// triangle is possible
if (N < 3)
return false;
// first sort the array
arr.sort();
// loop for all 3
// consecutive triplets
for (let i = 0; i < N - 2; i++)
// If triplet satisfies
// triangle condition, break
if (arr[i] + arr[i + 1] > arr[i + 2])
return true;
return false;
}
// Driver code
let arr = [5, 4, 3, 1, 2];
let N = arr.length;
if(isPossibleTriangle(arr, N))
document.write("Yes" );
else
document.write("No");
// This code is contributed by susmitakundugoaldanga.
</script>
Yes
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA