Given a list of positive integers, find the number of triangles we can form such that their side lengths are represented by three distinct entries of the input list.
(Inspiration comes from CR.)
Details
- A triangle can be formed if all permutations of the three side lengths \$a,b,c\$ satisfy the strict triangle inequality $$a + b > c.$$ (This means \$a+b > c\$, \$a+c>b\$ and \$b+c>a\$ must all hold.)
- The three side lengths \$a,b,c\$ must appear at distinct positions in the list, but do not necessarily have to be pairwise distinct.
- The order of the three numbers in the input list does not matter. If we consider a list
a
and the three numbersa[i], a[j], a[k]
(wherei,j,k
are pairwise different), then(a[i],a[j],a[k]), (a[i],a[k],a[j]), (a[j], a[i], a[k])
etc. all are considered as the same triangle. - The input list can assumed to contain at least 3 entries.
- You can assume that the input list is sorted in ascending order.
Examples
A small test program can be found here on Try it online!
Input, Output:
[1,2,3] 0
[1,1,1] 1
[1,1,1,1] 4
[1,2,3,4] 1
[3,4,5,7] 3
[1,42,69,666,1000000] 0
[12,23,34,45,56,67,78,89] 34
[1,2,3,4,5,6,7,8,9,10] 50
For the input of [1,2,3,...,n-1,n]
this is A002623.
For the input of [1,1,...,1]
(length n
) this is A000292.
For the input of the first n
Fibonacci numbers (A000045) this is A000004.
[1,1,1,1]
allows 4 "different" triangles, all[1,1,1]
, to be chosen using any three of the 1's? But, it's not 24 because the three 1's are chosen unordered, i.e. it's a subset of three indices rather than an ordered list? \$\endgroup\$