Dada una array no ordenada de enteros positivos, encuentre el número de triángulos que se pueden formar con tres elementos de array diferentes como tres lados de triángulos. Para que un triángulo sea posible a partir de 3 valores, la suma de cualquiera de los dos valores (o lados) debe ser mayor que el tercer valor (o tercer lado).
Ejemplos:
Input: arr= {4, 6, 3, 7}
Output: 3
Explanation: There are three triangles
possible {3, 4, 6}, {4, 6, 7} and {3, 6, 7}.
Note that {3, 4, 7} is not a possible triangle.
Input: arr= {10, 21, 22, 100, 101, 200, 300}.
Output: 6
Explanation: There can be 6 possible triangles:
{10, 21, 22}, {21, 100, 101}, {22, 100, 101},
{10, 100, 101}, {100, 101, 200} and {101, 200, 300}
Método 1 (Fuerza bruta) :
Acercarse:
El método de fuerza bruta consiste en ejecutar tres bucles y realizar un seguimiento del número de triángulos posibles hasta el momento. Los tres bucles seleccionan tres valores diferentes de una array. El ciclo más interno verifica la propiedad del triángulo que especifica que la suma de dos lados debe ser mayor que el valor del tercer lado).
Algoritmo:
- Ejecute tres bucles anidados, cada bucle comenzando desde el índice del bucle anterior hasta el final de la array, es decir, ejecute el primer bucle de 0 a n, el bucle j de i a nyk de j a n.
- Compruebe si array[i] + array[j] > array[k], es decir, la suma de dos lados es mayor que el tercero
- Verifique la condición (2) para todas las combinaciones de lados intercambiando i, j, k
- Si las tres condiciones coinciden, aumente el conteo.
- Imprime el conteo
Implementación:
C++
// C++ code to count the number of possible triangles using
// brute force approach
#include <bits/stdc++.h>
using namespace std;
// Function to count all possible triangles with arr[]
// elements
int findNumberOfTriangles(int arr[], int n)
{
// Count of triangles
int count = 0;
// The three loops select three different values from
// array
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// The innermost loop checks for the triangle
// property
for (int k = j + 1; k < n; k++)
// Sum of two sides is greater than the
// third
if (arr[i] + arr[j] > arr[k]
&& arr[i] + arr[k] > arr[j]
&& arr[k] + arr[j] > arr[i])
count++;
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 10, 21, 22, 100, 101, 200, 300 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Total number of triangles possible is "
<< findNumberOfTriangles(arr, size);
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
// C++ code to count the number of possible triangles using
// brute force approach
#include <stdio.h>
// Function to count all possible triangles with arr[]
// elements
int findNumberOfTriangles(int arr[], int n)
{
// Count of triangles
int count = 0;
// The three loops select three different values from
// array
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// The innermost loop checks for the triangle
// property
for (int k = j + 1; k < n; k++)
// Sum of two sides is greater than the
// third
if (arr[i] + arr[j] > arr[k]
&& arr[i] + arr[k] > arr[j]
&& arr[k] + arr[j] > arr[i])
count++;
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 10, 21, 22, 100, 101, 200, 300 };
int size = sizeof(arr) / sizeof(arr[0]);
printf("Total number of triangles possible is %d ",
findNumberOfTriangles(arr, size));
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java code to count the number of possible triangles using
// brute force approach
import java.io.*;
import java.util.*;
class GFG {
// Function to count all possible triangles with arr[]
// elements
static int findNumberOfTriangles(int arr[], int n)
{
// Sort the array
Arrays.sort(arr);
// Count of triangles
int count = 0;
// The three loops select three different values
// from array
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
if (arr[i] + arr[j] > arr[k])
count++;
return count;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 10, 21, 22, 100, 101, 200, 300 };
int size = arr.length;
System.out.println(
"Total number of triangles possible is "
+ findNumberOfTriangles(arr, size));
}
}
// This code is contributed by Sania Kumari Gupta
Python3
# Python3 code to count the number of
# possible triangles using brute
# force approach
# Function to count all possible
# triangles with arr[] elements
def findNumberOfTriangles(arr, n):
# Count of triangles
count = 0
# The three loops select three
# different values from array
for i in range(n):
for j in range(i + 1, n):
# The innermost loop checks for
# the triangle property
for k in range(j + 1, n):
# Sum of two sides is greater
# than the third
if (arr[i] + arr[j] > arr[k] and
arr[i] + arr[k] > arr[j] and
arr[k] + arr[j] > arr[i]):
count += 1
return count
# Driver code
arr = [ 10, 21, 22, 100, 101, 200, 300 ]
size = len(arr)
print("Total number of triangles possible is",
findNumberOfTriangles(arr, size))
# This code is contributed by shubhamsingh10
C#
// C# code to count the number of
// possible triangles using brute
// force approach
using System;
class GFG{
// Function to count all possible
// triangles with arr[] elements
static int findNumberOfTriangles(int[] arr, int n)
{
// Count of triangles
int count = 0;
// The three loops select three
// different values from array
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// The innermost loop checks for
// the triangle property
for (int k = j + 1; k < n; k++)
// Sum of two sides is greater
// than the third
if (
arr[i] + arr[j] > arr[k]
&& arr[i] + arr[k] > arr[j]
&& arr[k] + arr[j] > arr[i])
count++;
}
}
return count;
}
// Driver code
static public void Main ()
{
int[] arr = { 10, 21, 22, 100, 101, 200, 300 };
int size = arr.Length;
Console.WriteLine("Total number of triangles possible is "+findNumberOfTriangles(arr, size));
}
}
// This code is contributed by shubhamsingh10
Javascript
<script>
// Javascript program for the above approach
// Function to count all possible
// triangles with arr[] elements
function findNumberOfTriangles(arr, n)
{
// Count of triangles
let count = 0;
// The three loops select three
// different values from array
for (let i = 0; i < n; i++)
{
for (let j = i + 1; j < n; j++)
{
// The innermost loop checks for
// the triangle property
for (let k = j + 1; k < n; k++)
// Sum of two sides is greater
// than the third
if (
arr[i] + arr[j] > arr[k]
&& arr[i] + arr[k] > arr[j]
&& arr[k] + arr[j] > arr[i])
count++;
}
}
return count;
}
// Driver Code
let arr = [ 10, 21, 22, 100, 101, 200, 300 ];
let size = arr.length;
document.write( "Total number of triangles possible is "+
findNumberOfTriangles(arr, size));
// This code is contributed by souravghosh0416.
</script>
Producción:
Total number of triangles possible is 6
Análisis de Complejidad:
- Complejidad de tiempo: O(N^3) donde N es el tamaño de la array de entrada.
- Complejidad espacial: O(1)
Método 2 : este es un enfoque engañoso y eficiente para reducir la complejidad del tiempo de O (n ^ 3) a O (n ^ 2) donde se fijan dos lados de los triángulos y la cuenta se puede encontrar usando esos dos lados.
Acercarse:
Primero ordene la array en orden ascendente. Luego usa dos bucles. El lazo exterior para fijar el primer lado y el lazo interior para fijar el segundo lado y luego encontrar el índice más lejano del tercer lado (mayor que los índices de ambos lados) cuya longitud es menor que la suma de los otros dos lados. Por lo tanto, se puede encontrar un rango de valores de los terceros lados, donde se garantiza que su longitud es mayor que los otros lados individuales pero menor que la suma de ambos lados.
Algoritmo: Sean a, b y c tres lados. La siguiente condición debe cumplirse para un triángulo (la suma de dos lados es mayor que el tercer lado)
- a + b > c
- b + c > un
- a + c > b
Los siguientes son pasos para contar triángulos.
- Ordene la array en orden ascendente.
- Ahora ejecute un bucle anidado. El ciclo externo se ejecuta de principio a fin y el ciclo interno se ejecuta desde el índice + 1 del primer ciclo hasta el final. Tome el contador de bucles del primer bucle como i y el segundo bucle como j . Toma otra variable k = i + 2
- Ahora hay dos punteros i y j , donde array[i] y array[j] representan dos lados de los triángulos. Para i y j fijos , encuentre la cantidad de terceros lados que satisfagan las condiciones de un triángulo. es decir, encuentre el valor más grande de array[k] tal que array[i] + array[j] > array[k]
- Entonces, cuando obtengamos el valor más grande, entonces la cuenta del tercer lado es k – j , súmela a la cuenta total.
- Ahora sume todos los pares válidos de i y j donde i < j
Implementación:
C++
// C++ program to count number of triangles that can be
// formed from given array
#include <bits/stdc++.h>
using namespace std;
// Function to count all possible triangles with arr[]
// elements
int findNumberOfTriangles(int arr[], int n)
{
// Sort the array elements in non-decreasing order
sort(arr, arr + n);
// Initialize count of triangles
int count = 0;
// Fix the first element. We need to run till n-3
// as the other two elements are selected from
// arr[i+1...n-1]
for (int i = 0; i < n - 2; ++i) {
// Initialize index of the rightmost third
// element
int k = i + 2;
// Fix the second element
for (int j = i + 1; j < n; ++j) {
// Find the rightmost element which is smaller
// than the sum of two fixed elements The
// important thing to note here is, we use the
// previous value of k. If value of arr[i] +
// arr[j-1] was greater than arr[k], then arr[i]
// + arr[j] must be greater than k, because the
// array is sorted.
while (k < n && arr[i] + arr[j] > arr[k])
++k;
// Total number of possible triangles that can
// be formed with the two fixed elements is
// k - j - 1. The two fixed elements are arr[i]
// and arr[j]. All elements between arr[j+1]/ to
// arr[k-1] can form a triangle with arr[i] and
// arr[j]. One is subtracted from k because k is
// incremented one extra in above while loop. k
// will always be greater than j. If j becomes
// equal to k, then above loop will increment k,
// because arr[k]
// + arr[i] is always greater than arr[k]
if (k > j)
count += k - j - 1;
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 10, 21, 22, 100, 101, 200, 300 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Total number of triangles possible is "
<< findNumberOfTriangles(arr, size);
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
// C program to count number of triangles that can be
// formed from given array
#include <stdio.h>
#include <stdlib.h>
/* Following function is needed for library function
qsort(). Refer
http:// www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */
int comp(const void* a, const void* b)
{
return *(int*)a > *(int*)b;
}
// Function to count all possible triangles with arr[]
// elements
int findNumberOfTriangles(int arr[], int n)
{
// Sort the array elements in non-decreasing order
qsort(arr, n, sizeof(arr[0]), comp);
// Initialize count of triangles
int count = 0;
// Fix the first element. We need to run till n-3
// as the other two elements are selected from
// arr[i+1...n-1]
for (int i = 0; i < n - 2; ++i) {
// Initialize index of the rightmost third
// element
int k = i + 2;
// Fix the second element
for (int j = i + 1; j < n; ++j) {
// Find the rightmost element which is
// smaller than the sum of two fixed elements
// The important thing to note here is, we
// use the previous value of k. If value of
// arr[i] + arr[j-1] was greater than arr[k],
// then arr[i] + arr[j] must be greater than k,
// because the array is sorted.
while (k < n && arr[i] + arr[j] > arr[k])
++k;
// Total number of possible triangles that can
// be formed with the two fixed elements is
// k - j - 1. The two fixed elements are arr[i]
// and arr[j]. All elements between arr[j+1]/ to
// arr[k-1] can form a triangle with arr[i] and arr[j].
// One is subtracted from k because k is incremented
// one extra in above while loop.
// k will always be greater than j. If j becomes equal
// to k, then above loop will increment k, because arr[k]
// + arr[i] is always greater than arr[k]
if (k > j)
count += k - j - 1;
}
}
return count;
}
// Driver program to test above functionarr[j+1]
int main()
{
int arr[] = { 10, 21, 22, 100, 101, 200, 300 };
int size = sizeof(arr) / sizeof(arr[0]);
printf("Total number of triangles possible is %d ",
findNumberOfTriangles(arr, size));
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program to count number of triangles that can be
// formed from given array
import java.io.*;
import java.util.*;
class CountTriangles {
// Function to count all possible triangles with arr[]
// elements
static int findNumberOfTriangles(int arr[])
{
int n = arr.length;
// Sort the array elements in non-decreasing order
Arrays.sort(arr);
// Initialize count of triangles
int count = 0;
// Fix the first element. We need to run till n-3 as
// the other two elements are selected from
// arr[i+1...n-1]
for (int i = 0; i < n - 2; ++i) {
// Initialize index of the rightmost third
// element
int k = i + 2;
// Fix the second element
for (int j = i + 1; j < n; ++j) {
// Find the rightmost element which is
// smaller than the sum of two fixed
// elements The important thing to note here
// is, we use the previous value of k. If
// value of arr[i] + arr[j-1] was greater
// than arr[k], then arr[i] + arr[j] must be
// greater than k, because the array is
// sorted.
while (k < n && arr[i] + arr[j] > arr[k])
++k;
// Total number of possible triangles that
// can be formed with the two fixed elements
// is k - j - 1. The two fixed elements are
// arr[i] and arr[j]. All elements between
// arr[j+1] to arr[k-1] can form a triangle
// with arr[i] and arr[j]. One is subtracted
// from k because k is incremented one extra
// in above while loop. k will always be
// greater than j. If j becomes equal to k,
// then above loop will increment k, because
// arr[k] + arr[i] is always/ greater than
// arr[k]
if (k > j)
count += k - j - 1;
}
}
return count;
}
public static void main(String[] args)
{
int arr[] = { 10, 21, 22, 100, 101, 200, 300 };
System.out.println("Total number of triangles is "
+ findNumberOfTriangles(arr));
}
}
// This code is contributed by Sania Kumari Gupta
Python3
# Python function to count all possible triangles with arr[]
# elements
def findnumberofTriangles(arr):
# Sort array and initialize count as 0
n = len(arr)
arr.sort()
count = 0
# Fix the first element. We need to run till n-3 as
# the other two elements are selected from arr[i + 1...n-1]
for i in range(0, n-2):
# Initialize index of the rightmost third element
k = i + 2
# Fix the second element
for j in range(i + 1, n):
# Find the rightmost element which is smaller
# than the sum of two fixed elements
# The important thing to note here is, we use
# the previous value of k. If value of arr[i] +
# arr[j-1] was greater than arr[k], then arr[i] +
# arr[j] must be greater than k, because the array
# is sorted.
while (k < n and arr[i] + arr[j] > arr[k]):
k += 1
# Total number of possible triangles that can be
# formed with the two fixed elements is k - j - 1.
# The two fixed elements are arr[i] and arr[j]. All
# elements between arr[j + 1] to arr[k-1] can form a
# triangle with arr[i] and arr[j]. One is subtracted
# from k because k is incremented one extra in above
# while loop. k will always be greater than j. If j
# becomes equal to k, then above loop will increment k,
# because arr[k] + arr[i] is always greater than arr[k]
if(k>j):
count += k - j - 1
return count
# Driver function to test above function
arr = [10, 21, 22, 100, 101, 200, 300]
print ("Number of Triangles:", findnumberofTriangles(arr))
# This code is contributed by Devesh Agrawal
C#
// C# program to count number
// of triangles that can be
// formed from given array
using System;
class GFG {
// Function to count all
// possible triangles
// with arr[] elements
static int findNumberOfTriangles(int[] arr)
{
int n = arr.Length;
// Sort the array elements
// in non-decreasing order
Array.Sort(arr);
// Initialize count
// of triangles
int count = 0;
// Fix the first element. We
// need to run till n-3 as
// the other two elements are
// selected from arr[i+1...n-1]
for (int i = 0; i < n - 2; ++i) {
// Initialize index of the
// rightmost third element
int k = i + 2;
// Fix the second element
for (int j = i + 1; j < n; ++j) {
/* Find the rightmost element
which is smaller than the sum
of two fixed elements. The
important thing to note here
is, we use the previous value
of k. If value of arr[i] +
arr[j-1] was greater than arr[k],
then arr[i] + arr[j] must be
greater than k, because the
array is sorted. */
while (k < n && arr[i] + arr[j] > arr[k])
++k;
/* Total number of possible triangles
that can be formed with the two
fixed elements is k - j - 1. The
two fixed elements are arr[i] and
arr[j]. All elements between arr[j+1]
to arr[k-1] can form a triangle with
arr[i] and arr[j]. One is subtracted
from k because k is incremented one
extra in above while loop. k will
always be greater than j. If j becomes
equal to k, then above loop will
increment k, because arr[k] + arr[i]
is always/ greater than arr[k] */
if (k > j)
count += k - j - 1;
}
}
return count;
}
// Driver Code
public static void Main()
{
int[] arr = { 10, 21, 22, 100,
101, 200, 300 };
Console.WriteLine("Total number of triangles is " + findNumberOfTriangles(arr));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to count number
// of triangles that can be
// formed from given array
// Function to count all
// possible triangles with
// arr[] element
function findNumberOfTriangles($arr)
{
$n = count($arr);
// Sort the array elements
// in non-decreasing order
sort($arr);
// Initialize count
// of triangles
$count = 0;
// Fix the first element.
// We need to run till n-3
// as the other two elements
// are selected from
// arr[i+1...n-1]
for ($i = 0; $i < $n - 2; ++$i)
{
// Initialize index of the
// rightmost third element
$k = $i + 2;
// Fix the second element
for ($j = $i + 1; $j < $n; ++$j)
{
/* Find the rightmost element
which is smaller than the sum
of two fixed elements. The
important thing to note here
is, we use the previous value
of k. If value of arr[i] +
arr[j-1] was greater than
arr[k], then arr[i] +
arr[j] must be greater than k,
because the array is sorted. */
while ($k < $n && $arr[$i] +
$arr[$j] > $arr[$k])
++$k;
/* Total number of possible
triangles that can be
formed with the two fixed
elements is k - j - 1.
The two fixed elements are
arr[i] and arr[j]. All
elements between arr[j+1]
to arr[k-1] can form a
triangle with arr[i] and
arr[j]. One is subtracted
from k because k is incremented
one extra in above while loop.
k will always be greater than j.
If j becomes equal to k, then
above loop will increment k,
because arr[k] + arr[i] is
always/ greater than arr[k] */
if($k>$j)
$count += $k - $j - 1;
}
}
return $count;
}
// Driver code
$arr = array(10, 21, 22, 100,
101, 200, 300);
echo"Total number of triangles is ",
findNumberOfTriangles($arr);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to count number of triangles that can be
// formed from given array
// Function to count all possible triangles with arr[]
// elements
function findNumberOfTriangles(arr)
{
let n = arr.length;
// Sort the array elements in non-decreasing order
arr.sort((a, b) => a-b);
// Initialize count of triangles
let count = 0;
// Fix the first element. We
// need to run till n-3 as
// the other two elements are
// selected from arr[i+1...n-1]
for (let i = 0; i < n - 2; ++i) {
// Initialize index of the
// rightmost third element
let k = i + 2;
// Fix the second element
for (let j = i + 1; j < n; ++j) {
// Find the rightmost element which is
// smaller than the sum of two fixed elements
// The important thing to note here is, we
// use the previous value of k. If value of
// arr[i] + arr[j-1] was greater than arr[k],
// then arr[i] + arr[j] must be greater than k,
// because the array is sorted.
while (k < n && arr[i] + arr[j] > arr[k])
++k;
// Total number of possible triangles that can
// be formed with the two fixed elements is
// k - j - 1. The two fixed elements are arr[i]
// and arr[j]. All elements between arr[j+1]/ to
// arr[k-1] can form a triangle with arr[i] and arr[j].
// One is subtracted from k because k is incremented
// one extra in above while loop.
// k will always be greater than j. If j becomes equal
// to k, then above loop will increment k, because arr[k]
// + arr[i] is always greater than arr[k]
if (k > j)
count += k - j - 1;
}
}
return count;
}
// Driver code
let arr = [ 10, 21, 22, 100, 101, 200, 300 ];
let size = arr.length;
document.write("Total number of triangles possible is " + findNumberOfTriangles(arr, size));
// This code is contributed by Manoj
</script>
Producción:
Total number of triangles possible is 6
Análisis de Complejidad:
- Complejidad de tiempo: O(n^2).
La complejidad del tiempo se ve más debido a 3 bucles anidados. Se puede observar que k se inicializa solo una vez en el bucle más externo. El ciclo más interno se ejecuta como máximo en el tiempo O(n) para cada iteración del ciclo más externo, porque k comienza desde i+2 y sube hasta n para todos los valores de j. Por lo tanto, la complejidad del tiempo es O(n^2). - Complejidad espacial: O(1).
No se requiere espacio adicional. Entonces la complejidad del espacio es constante.
Método 3: la complejidad del tiempo se puede reducir en gran medida utilizando métodos de dos punteros en solo dos bucles anidados.
Acercarse:
Primero ordene la array y ejecute un bucle anidado, corrija un índice y luego intente fijar un índice superior e inferior dentro del cual podamos usar todas las longitudes para formar un triángulo con ese índice fijo.
Algoritmo:
- Ordene la array y luego tome tres variables l, r e i, apuntando al inicio, al final-1 y al elemento de la array comenzando desde el final de la array.
- Recorra la array desde el final (n-1 a 1), y para cada iteración mantenga el valor de l = 0 y r = i-1
- Ahora bien, si se puede formar un triángulo usando arr[l] y arr[r], entonces los triángulos obviamente se pueden formar
a partir de a[l+1], a[l+2]…..a[r-1], arr[r] y a[i], porque la array está ordenada , lo que se puede calcular directamente usando (rl). y luego disminuya el valor de r y continúe el ciclo hasta que l sea menor que r- Si no se puede formar un triángulo usando arr[l] y arr[r] entonces incremente el valor de l y continúe el bucle hasta que l sea menor que r
- Por lo tanto, se reduce la complejidad general de iterar
a través de todos los elementos de la array.
Implementación:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
void CountTriangles(vector<int> A)
{
int n = A.size();
sort(A.begin(), A.end());
int count = 0;
for (int i = n - 1; i >= 1; i--) {
int l = 0, r = i - 1;
while (l < r) {
if (A[l] + A[r] > A[i]) {
// If it is possible with a[l], a[r]
// and a[i] then it is also possible
// with a[l+1]..a[r-1], a[r] and a[i]
count += r - l;
// checking for more possible solutions
r--;
}
else
// if not possible check for
// higher values of arr[l]
l++;
}
}
cout << "No of possible solutions: " << count;
}
int main()
{
vector<int> A = { 4, 3, 5, 7, 6 };
CountTriangles(A);
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG {
static void CountTriangles(int[] A)
{
int n = A.length;
Arrays.sort(A);
int count = 0;
for (int i = n - 1; i >= 1; i--) {
int l = 0, r = i - 1;
while (l < r) {
if (A[l] + A[r] > A[i]) {
// If it is possible with a[l], a[r]
// and a[i] then it is also possible
// with a[l+1]..a[r-1], a[r] and a[i]
count += r - l;
// checking for more possible solutions
r--;
}
else // if not possible check for
// higher values of arr[l]
{
l++;
}
}
}
System.out.print("No of possible solutions: " + count);
}
// Driver Code
public static void main(String[] args)
{
int[] A = { 4, 3, 5, 7, 6 };
CountTriangles(A);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python implementation of the above approach
def CountTriangles( A):
n = len(A);
A.sort();
count = 0;
for i in range(n - 1, 0, -1):
l = 0;
r = i - 1;
while(l < r):
if(A[l] + A[r] > A[i]):
# If it is possible with a[l], a[r]
# and a[i] then it is also possible
# with a[l + 1]..a[r-1], a[r] and a[i]
count += r - l;
# checking for more possible solutions
r -= 1;
else:
# if not possible check for
# higher values of arr[l]
l += 1;
print("No of possible solutions: ", count);
# Driver Code
if __name__ == '__main__':
A = [ 4, 3, 5, 7, 6 ];
CountTriangles(A);
# This code is contributed by PrinciRaj1992
C#
// C# implementation of the above approach
using System;
class GFG {
static void CountTriangles(int[] A)
{
int n = A.Length;
Array.Sort(A);
int count = 0;
for (int i = n - 1; i >= 1; i--) {
int l = 0, r = i - 1;
while (l < r) {
if (A[l] + A[r] > A[i]) {
// If it is possible with a[l], a[r]
// and a[i] then it is also possible
// with a[l+1]..a[r-1], a[r] and a[i]
count += r - l;
// checking for more possible solutions
r--;
}
else // if not possible check for
// higher values of arr[l]
{
l++;
}
}
}
Console.Write("No of possible solutions: " + count);
}
// Driver Code
public static void Main(String[] args)
{
int[] A = { 4, 3, 5, 7, 6 };
CountTriangles(A);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript implementation of the above approach
function CountTriangles(A) {
var n = A.length;
A.sort();
var count = 0;
for (i = n - 1; i >= 1; i--) {
var l = 0, r = i - 1;
while (l < r) {
if (A[l] + A[r] > A[i]) {
// If it is possible with a[l], a[r]
// and a[i] then it is also possible
// with a[l+1]..a[r-1], a[r] and a[i]
count += r - l;
// checking for more possible solutions
r--;
} else // if not possible check for
// higher values of arr[l]
{
l++;
}
}
}
document.write("No of possible solutions: " + count);
}
// Driver Code
var A = [ 4, 3, 5, 7, 6 ];
CountTriangles(A);
// This code is contributed by aashish1995
</script>
Producción:
No of possible solutions: 9
Análisis de Complejidad:
- Complejidad temporal: O(n^2).
Como se utilizan dos bucles anidados, las iteraciones generales en comparación con el método anterior se reducen en gran medida. - Complejidad espacial: O(1).
Como no se requiere espacio adicional, la complejidad del espacio es constante
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