Count the number of possible triangles
The problem at hand is to determine the number of possible triangles that can be formed from a given collection of line segments. In order for three line segments to form a triangle, the sum of the lengths of any two sides of the triangle must be greater than the length of the third side. This concept is known as the triangle inequality theorem.
Problem Statement
Given an array of integers, each representing the length of a line segment, we need to count the number of unique combinations of line segments that can form triangles.
Example
Let's take an array collection1
with the following values: [5, 9, 2, 7, 8, 3]
.
Here, we can find the following triangles:
- 2 + 3 > 5
- 2 + 5 > 7
- 2 + 7 > 9
- 2 + 8 > 10
- 3 + 5 > 8
- 3 + 7 > 10
- 5 + 7 > 12
- 7 + 8 > 15
- 8 + 9 > 17
- 5 + 9 > 14
Therefore, there are 10 possible triangles that can be formed from the given collection.
Idea to Solve
To solve this problem, we need to iterate through all possible combinations of three line segments and check whether they satisfy the triangle inequality theorem. If they do, we increment a counter to keep track of the number of valid triangles.
Pseudocode
function display(collection[], size):
for i from 0 to size - 1:
print collection[i]
print newline
function possible_triangles(collection[], size):
if size < 3:
return
display(collection, size)
triangle = 0
for first from 0 to size - 3:
for second from first + 1 to size - 2:
for third from second + 1 to size - 1:
if collection[first] + collection[second] > collection[third] and
collection[second] + collection[third] > collection[first] and
collection[first] + collection[third] > collection[second]:
triangle = triangle + 1
print "Possible Triangles:", triangle, newline
function main():
collection1 = [5, 9, 2, 7, 8, 3]
collection2 = [7, 3, 9, 2, 55, 23, 12, 4]
size = size_of(collection1)
possible_triangles(collection1, size)
size = size_of(collection2)
possible_triangles(collection2, size)
main()
Algorithm Explanation
- The
display
function simply prints the elements of an array. - The
possible_triangles
function takes an array of line segment lengths and its size as inputs. - It iterates through all possible combinations of three line segments using nested loops.
- Inside the innermost loop, it checks whether the lengths of the three line segments satisfy the triangle inequality theorem.
- If they do, the
triangle
counter is incremented. - The
main
function defines two arrayscollection1
andcollection2
and calls thepossible_triangles
function for each collection.
Code Solution
// C program
// Count the number of possible triangles
#include <stdio.h>
//Display array element
void display(int collection[], int size)
{
for (int i = 0; i < size; i++)
{
printf(" %d", collection[i]);
}
printf("\n");
}
//Find number of triangles are possible in given collection
void possible_triangles(int collection[], int size)
{
if (size < 2)
{
return;
}
//Display array data
display(collection, size);
// Loop controlling variables
int first, second, third;
// Triangle counter
int triangle = 0;
for (first = 0; first < size; ++first)
{
for (second = first + 1; second < size; ++second)
{
for (third = second + 1; third < size; ++third)
{
if (collection[first] + collection[second] > collection[third] && collection[second] + collection[third] > collection[first] && collection[first] + collection[third] > collection[second])
{
triangle++;
}
}
}
}
//Print calculated result
printf(" Possible Triangles : %d \n\n", triangle);
}
int main()
{
int collection1[] = {
5 , 9 , 2 , 7 , 8 , 3
};
int collection2[] = {
7 , 3 , 9 , 2 , 55 , 23 , 12 , 4
};
//Test case
int size = sizeof(collection1) / sizeof(collection1[0]);
possible_triangles(collection1, size);
size = sizeof(collection2) / sizeof(collection2[0]);
possible_triangles(collection2, size);
return 0;
}
Output
5 9 2 7 8 3
Possible Triangles : 10
7 3 9 2 55 23 12 4
Possible Triangles : 5
/*
Java program
Count the number of possible triangles
*/
class Triangles
{
//Display array element
public void display(int[] collection, int size)
{
for (int i = 0; i < size; i++)
{
System.out.print(" " + collection[i]);
}
System.out.print("\n");
}
//Find number of triangles are possible in given collection
public void possible_triangles(int[] collection, int size)
{
if (size < 2)
{
return;
}
//Display array data
display(collection, size);
// Loop controlling variables
int first, second, third;
// Triangle counter
int triangle = 0;
for (first = 0; first < size; ++first)
{
for (second = first + 1; second < size; ++second)
{
for (third = second + 1; third < size; ++third)
{
if (collection[first] + collection[second] > collection[third] && collection[second] + collection[third] > collection[first] && collection[first] + collection[third] > collection[second])
{
triangle++;
}
}
}
}
//Print calculated result
System.out.print(" Possible Triangles : " + triangle + " \n\n");
}
public static void main(String[] args)
{
Triangles obj = new Triangles();
int[] collection1 = {
5 , 9 , 2 , 7 , 8 , 3
};
int[] collection2 = {
7 , 3 , 9 , 2 , 55 , 23 , 12 , 4
};
//Test case
int size = collection1.length;
obj.possible_triangles(collection1, size);
size = collection2.length;
obj.possible_triangles(collection2, size);
}
}
Output
5 9 2 7 8 3
Possible Triangles : 10
7 3 9 2 55 23 12 4
Possible Triangles : 5
//Include header file
#include <iostream>
using namespace std;
/*
C++ program
Count the number of possible triangles
*/
class Triangles
{
public:
//Display array element
void display(int collection[], int size)
{
for (int i = 0; i < size; i++)
{
cout << " " << collection[i];
}
cout << "\n";
}
//Find number of triangles are possible in given collection
void possible_triangles(int collection[], int size)
{
if (size < 2)
{
return;
}
//Display array data
this->display(collection, size);
// Loop controlling variables
int first, second, third;
// Triangle counter
int triangle = 0;
for (first = 0; first < size; ++first)
{
for (second = first + 1; second < size; ++second)
{
for (third = second + 1; third < size; ++third)
{
if (collection[first] + collection[second] > collection[third] && collection[second] + collection[third] > collection[first] && collection[first] + collection[third] > collection[second])
{
triangle++;
}
}
}
}
//Print calculated result
cout << " Possible Triangles : " << triangle << " \n\n";
}
};
int main()
{
Triangles obj = Triangles();
int collection1[] = {
5 , 9 , 2 , 7 , 8 , 3
};
int collection2[] = {
7 , 3 , 9 , 2 , 55 , 23 , 12 , 4
};
//Test case
int size = sizeof(collection1) / sizeof(collection1[0]);
obj.possible_triangles(collection1, size);
size = sizeof(collection2) / sizeof(collection2[0]);
obj.possible_triangles(collection2, size);
return 0;
}
Output
5 9 2 7 8 3
Possible Triangles : 10
7 3 9 2 55 23 12 4
Possible Triangles : 5
//Include namespace system
using System;
/*
C# program
Count the number of possible triangles
*/
class Triangles
{
//Display array element
public void display(int[] collection, int size)
{
for (int i = 0; i < size; i++)
{
Console.Write(" " + collection[i]);
}
Console.Write("\n");
}
//Find number of triangles are possible in given collection
public void possible_triangles(int[] collection, int size)
{
if (size < 2)
{
return;
}
//Display array data
display(collection, size);
// Loop controlling variables
int first, second, third;
// Triangle counter
int triangle = 0;
for (first = 0; first < size; ++first)
{
for (second = first + 1; second < size; ++second)
{
for (third = second + 1; third < size; ++third)
{
if (collection[first] + collection[second] > collection[third] && collection[second] + collection[third] > collection[first] && collection[first] + collection[third] > collection[second])
{
triangle++;
}
}
}
}
//Print calculated result
Console.Write(" Possible Triangles : " + triangle + " \n\n");
}
public static void Main(String[] args)
{
Triangles obj = new Triangles();
int[] collection1 = {
5 , 9 , 2 , 7 , 8 , 3
};
int[] collection2 = {
7 , 3 , 9 , 2 , 55 , 23 , 12 , 4
};
//Test case
int size = collection1.Length;
obj.possible_triangles(collection1, size);
size = collection2.Length;
obj.possible_triangles(collection2, size);
}
}
Output
5 9 2 7 8 3
Possible Triangles : 10
7 3 9 2 55 23 12 4
Possible Triangles : 5
<?php
/*
Php program
Count the number of possible triangles
*/
class Triangles
{
//Display array element
public function display( & $collection, $size)
{
for ($i = 0; $i < $size; $i++)
{
echo " ". $collection[$i];
}
echo "\n";
}
//Find number of triangles are possible in given collection
public function possible_triangles( & $collection, $size)
{
if ($size < 2)
{
return;
}
//Display array data
$this->display($collection, $size);
// Triangle counter
$triangle = 0;
for ($first = 0; $first < $size; ++$first)
{
for ($second = $first + 1; $second < $size; ++$second)
{
for ($third = $second + 1; $third < $size; ++$third)
{
if ($collection[$first] + $collection[$second] > $collection[$third] && $collection[$second] + $collection[$third] > $collection[$first] && $collection[$first] + $collection[$third] > $collection[$second])
{
$triangle++;
}
}
}
}
//Print calculated result
echo " Possible Triangles : ". $triangle ." \n\n";
}
}
function main()
{
$obj = new Triangles();
$collection1 = array(5, 9, 2, 7, 8, 3);
$collection2 = array(7, 3, 9, 2, 55, 23, 12, 4);
//Test case
$size = count($collection1);
$obj->possible_triangles($collection1, $size);
$size = count($collection2);
$obj->possible_triangles($collection2, $size);
}
main();
Output
5 9 2 7 8 3
Possible Triangles : 10
7 3 9 2 55 23 12 4
Possible Triangles : 5
/*
Node Js program
Count the number of possible triangles
*/
class Triangles
{
//Display array element
display(collection, size)
{
for (var i = 0; i < size; i++)
{
process.stdout.write(" " + collection[i]);
}
process.stdout.write("\n");
}
//Find number of triangles are possible in given collection
possible_triangles(collection, size)
{
if (size < 2)
{
return;
}
//Display array data
this.display(collection, size);
// Triangle counter
var triangle = 0;
for (first = 0; first < size; ++first)
{
for (second = first + 1; second < size; ++second)
{
for (third = second + 1; third < size; ++third)
{
if (collection[first] + collection[second] > collection[third] && collection[second] + collection[third] > collection[first] && collection[first] + collection[third] > collection[second])
{
triangle++;
}
}
}
}
//Print calculated result
process.stdout.write(" Possible Triangles : " + triangle + " \n\n");
}
}
function main()
{
var obj = new Triangles();
var collection1 = [5, 9, 2, 7, 8, 3];
var collection2 = [7, 3, 9, 2, 55, 23, 12, 4];
//Test case
var size = collection1.length;
obj.possible_triangles(collection1, size);
size = collection2.length;
obj.possible_triangles(collection2, size);
}
main();
Output
5 9 2 7 8 3
Possible Triangles : 10
7 3 9 2 55 23 12 4
Possible Triangles : 5
# Python 3 program
# Count the number of possible triangles
class Triangles :
# Display array element
def display(self, collection, size) :
i = 0
while (i < size) :
print(" ", collection[i], end = "")
i += 1
print("\n", end = "")
# Find number of triangles are possible in given collection
def possible_triangles(self, collection, size) :
if (size < 2) :
return
# Display array data
self.display(collection, size)
# Loop controlling variables
first = 0
second = 0
third = 0
# Triangle counter
triangle = 0
while (first < size) :
second = first + 1
while (second < size) :
third = second + 1
while (third < size) :
if (collection[first] + collection[second] > collection[third]
and collection[second] + collection[third] > collection[first]
and collection[first] + collection[third] > collection[second]) :
triangle += 1
third += 1
second += 1
first += 1
# Print calculated result
print(" Possible Triangles : ", triangle ," \n\n", end = "")
def main() :
obj = Triangles()
collection1 = [5, 9, 2, 7, 8, 3]
collection2 = [7, 3, 9, 2, 55, 23, 12, 4]
# Test case
size = len(collection1)
obj.possible_triangles(collection1, size)
size = len(collection2)
obj.possible_triangles(collection2, size)
if __name__ == "__main__": main()
Output
5 9 2 7 8 3
Possible Triangles : 10
7 3 9 2 55 23 12 4
Possible Triangles : 5
# Ruby program
# Count the number of possible triangles
class Triangles
# Display array element
def display(collection, size)
i = 0
while (i < size)
print(" ", collection[i])
i += 1
end
print("\n")
end
# Find number of triangles are possible in given collection
def possible_triangles(collection, size)
if (size < 2)
return
end
# Display array data
self.display(collection, size)
# Loop controlling variables
first = 0
second = 0
third = 0
# Triangle counter
triangle = 0
while (first < size)
second = first + 1
while (second < size)
third = second + 1
while (third < size)
if (collection[first] + collection[second] > collection[third] && collection[second] + collection[third] > collection[first] && collection[first] + collection[third] > collection[second])
triangle += 1
end
third += 1
end
second += 1
end
first += 1
end
# Print calculated result
print(" Possible Triangles : ", triangle ," \n\n")
end
end
def main()
obj = Triangles.new()
collection1 = [5, 9, 2, 7, 8, 3]
collection2 = [7, 3, 9, 2, 55, 23, 12, 4]
# Test case
size = collection1.length
obj.possible_triangles(collection1, size)
size = collection2.length
obj.possible_triangles(collection2, size)
end
main()
Output
5 9 2 7 8 3
Possible Triangles : 10
7 3 9 2 55 23 12 4
Possible Triangles : 5
/*
Scala program
Count the number of possible triangles
*/
class Triangles
{
//Display array element
def display(collection: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + collection(i));
i += 1;
}
print("\n");
}
//Find number of triangles are possible in given collection
def possible_triangles(collection: Array[Int], size: Int): Unit = {
if (size < 2)
{
return;
}
//Display array data
display(collection, size);
// Loop controlling variables
var first: Int = 0;
var second: Int = 0;
var third: Int = 0;
// Triangle counter
var triangle: Int = 0;
while (first < size)
{
second = first + 1;
while (second < size)
{
third = second + 1;
while (third < size)
{
if (collection(first) + collection(second) > collection(third) && collection(second) + collection(third) > collection(first) && collection(first) + collection(third) > collection(second))
{
triangle += 1;
}
third += 1;
}
second += 1;
}
first += 1;
}
//Print calculated result
print(" Possible Triangles : " + triangle + " \n\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: Triangles = new Triangles();
var collection1: Array[Int] = Array(5, 9, 2, 7, 8, 3);
var collection2: Array[Int] = Array(7, 3, 9, 2, 55, 23, 12, 4);
//Test case
var size: Int = collection1.length;
obj.possible_triangles(collection1, size);
size = collection2.length;
obj.possible_triangles(collection2, size);
}
}
Output
5 9 2 7 8 3
Possible Triangles : 10
7 3 9 2 55 23 12 4
Possible Triangles : 5
/*
Swift 4 program
Count the number of possible triangles
*/
class Triangles
{
//Display array element
func display(_ collection: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", collection[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Find number of triangles are possible in given collection
func possible_triangles(_ collection: [Int], _ size: Int)
{
if (size < 2)
{
return;
}
//Display array data
self.display(collection, size);
// Loop controlling variables
var first: Int = 0;
var second: Int = 0;
var third: Int = 0;
// Triangle counter
var triangle: Int = 0;
while (first < size)
{
second = first + 1;
while (second < size)
{
third = second + 1;
while (third < size)
{
if (collection[first] + collection[second] > collection[third] && collection[second] + collection[third] > collection[first] && collection[first] + collection[third] > collection[second])
{
triangle += 1;
}
third += 1;
}
second += 1;
}
first += 1;
}
//Print calculated result
print(" Possible Triangles : ", triangle ," \n");
}
}
func main()
{
let obj: Triangles = Triangles();
let collection1: [Int] = [5, 9, 2, 7, 8, 3];
let collection2: [Int] = [7, 3, 9, 2, 55, 23, 12, 4];
//Test case
var size: Int = collection1.count;
obj.possible_triangles(collection1, size);
size = collection2.count;
obj.possible_triangles(collection2, size);
}
main();
Output
5 9 2 7 8 3
Possible Triangles : 10
7 3 9 2 55 23 12 4
Possible Triangles : 5
Time Complexity
The time complexity of the given algorithm is O(n^3), where n is the number of line segments in the collection. This is because we have three nested loops, each iterating up to the size of the collection. Therefore, the algorithm's performance will degrade as the size of the collection increases.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment