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:

1. 2 + 3 > 5
2. 2 + 5 > 7
3. 2 + 7 > 9
4. 2 + 8 > 10
5. 3 + 5 > 8
6. 3 + 7 > 10
7. 5 + 7 > 12
8. 7 + 8 > 15
9. 8 + 9 > 17
10. 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

1. The display function simply prints the elements of an array.
2. The possible_triangles function takes an array of line segment lengths and its size as inputs.
3. It iterates through all possible combinations of three line segments using nested loops.
4. Inside the innermost loop, it checks whether the lengths of the three line segments satisfy the triangle inequality theorem.
5. If they do, the triangle counter is incremented.
6. The main function defines two arrays collection1 and collection2 and calls the possible_triangles function for each collection.

Code Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

// 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;
}

  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);
	}
}

 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;
}

 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);
	}
}

 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();

 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();

 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()

  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()

 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);
	}
}

 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();

  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.