Dada una array de N enteros donde arr[i] denota el número de palos de longitud 2 i . La tarea es encontrar el número de triángulos posibles con longitudes dadas que tengan un área ≥ 0 .
Nota: cada palo solo se puede usar una vez.
Ejemplos:
Entrada: a[] = {1, 2, 2, 2, 2}
Salida: 3
Todos los triángulos posibles son:
(2 0 , 2 4 , 2 4 ), (2 1 , 2 3 , 2 3 ), (2 1 , 2 2 , 2 2 ).Entrada: a[] = {3, 3, 3}
Salida: 3
Planteamiento: La observación principal es que los triángulos con área ≥ 0 solo se pueden formar si hay tres palos de la misma longitud o uno diferente y dos palos de la misma longitud. Por lo tanto, iterar con avidez desde atrás y contar el número de pares de palos de la misma longitud disponibles, que es arr[i] / 2 . Pero si queda un palo, entonces se usa un par y un palo para formar un triángulo. Al final se calcula el número total de palos que quedan que es 2* pares y el número de triángulos que se pueden formar con estos palos restantes será (2* pares)/3 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// number of positive area triangles
int countTriangles(int a[], int n)
{
// To store the count of
// total triangles
int cnt = 0;
// To store the count of pairs of sticks
// with equal lengths
int pairs = 0;
// Back-traverse and count
// the number of triangles
for (int i = n - 1; i >= 0; i--) {
// Count the number of pairs
pairs += a[i] / 2;
// If we have one remaining stick
// and we have a pair
if (a[i] % 2 == 1 && pairs > 0) {
// Count 1 triangle
cnt += 1;
// Reduce one pair
pairs -= 1;
}
}
// Count the remaining triangles
// that can be formed
cnt += (2 * pairs) / 3;
return cnt;
}
// Driver code
int main()
{
int a[] = { 1, 2, 2, 2, 2 };
int n = sizeof(a) / sizeof(a[0]);
cout << countTriangles(a, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the
// number of positive area triangles
static int countTriangles(int a[], int n)
{
// To store the count of
// total triangles
int cnt = 0;
// To store the count of pairs of sticks
// with equal lengths
int pairs = 0;
// Back-traverse and count
// the number of triangles
for (int i = n - 1; i >= 0; i--)
{
// Count the number of pairs
pairs += a[i] / 2;
// If we have one remaining stick
// and we have a pair
if (a[i] % 2 == 1 && pairs > 0)
{
// Count 1 triangle
cnt += 1;
// Reduce one pair
pairs -= 1;
}
}
// Count the remaining triangles
// that can be formed
cnt += (2 * pairs) / 3;
return cnt;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 2, 2, 2, 2 };
int n = a.length;
System.out.println(countTriangles(a, n));
}
}
// This code is contributed by Code_Mech.
Python3
# Python3 implementation of the approach # Function to return the # number of positive area triangles def countTriangles(a, n): # To store the count of # total triangles cnt = 0 # To store the count of pairs of sticks # with equal lengths pairs = 0 # Back-traverse and count # the number of triangles for i in range(n - 1, -1, -1): # Count the number of pairs pairs += a[i] // 2 # If we have one remaining stick # and we have a pair if (a[i] % 2 == 1 and pairs > 0): # Count 1 triangle cnt += 1 # Reduce one pair pairs -= 1 # Count the remaining triangles # that can be formed cnt += (2 * pairs) // 3 return cnt # Driver code a = [1, 2, 2, 2, 2] n = len(a) print(countTriangles(a, n)) # This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the
// number of positive area triangles
static int countTriangles(int []a, int n)
{
// To store the count of
// total triangles
int cnt = 0;
// To store the count of pairs of sticks
// with equal lengths
int pairs = 0;
// Back-traverse and count
// the number of triangles
for (int i = n - 1; i >= 0; i--)
{
// Count the number of pairs
pairs += a[i] / 2;
// If we have one remaining stick
// and we have a pair
if (a[i] % 2 == 1 && pairs > 0)
{
// Count 1 triangle
cnt += 1;
// Reduce one pair
pairs -= 1;
}
}
// Count the remaining triangles
// that can be formed
cnt += (2 * pairs) / 3;
return cnt;
}
// Driver code
public static void Main()
{
int []a = { 1, 2, 2, 2, 2 };
int n = a.Length;
Console.WriteLine(countTriangles(a, n));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
// Function to return the
// number of positive area triangles
Function countTriangles($a, $n)
{
// To store the count of
// total triangles
$cnt = 0;
// To store the count of pairs of sticks
// with equal lengths
$pairs = 0;
// Back-traverse and count
// the number of triangles
for ($i = $n - 1; $i >= 0; $i--)
{
// Count the number of pairs
$pairs += $a[$i] / 2;
// If we have one remaining stick
// and we have a pair
if ($a[$i] % 2 == 1 && $pairs > 0)
{
// Count 1 triangle
$cnt += 1;
// Reduce one pair
$pairs -= 1;
}
}
// Count the remaining triangles
// that can be formed
$cnt += (int)((2 * $pairs) / 3);
return $cnt;
}
// Driver code
$a = array(1, 2, 2, 2, 2 );
$n = sizeof($a);
echo(countTriangles($a, $n));
// This code is contributed by Code_Mech.
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the number
// of positive area triangles
function countTriangles(a , n)
{
// To store the count of
// total triangles
var cnt = 0;
// To store the count of pairs
// of sticks with equal lengths
var pairs = 0;
// Back-traverse and count
// the number of triangles
for(let i = n - 1; i >= 0; i--)
{
// Count the number of pairs
pairs += a[i] / 2;
// If we have one remaining stick
// and we have a pair
if (a[i] % 2 == 1 && pairs > 0)
{
// Count 1 triangle
cnt += 1;
// Reduce one pair
pairs -= 1;
}
}
// Count the remaining triangles
// that can be formed
cnt += parseInt((2 * pairs) / 3);
return cnt;
}
// Driver code
var a = [ 1, 2, 2, 2, 2 ];
var n = a.length;
document.write(countTriangles(a, n));
// This code is contributed by aashish1995
</script>
Producción:
3
Complejidad temporal: O(n)
Espacio auxiliar: O(1)