We say a 3-tuple of positive real numbers (x1, x2, x3) is legal if a triangle can have sides of length x1, x2 and x3. Gi
Posted: Sat Feb 19, 2022 3:23 pm
We say a 3-tuple of positive real numbers (x1, x2, x3) is legal
if a triangle can have sides of length x1, x2 and x3. Given a list
of n positive real numbers {x1, . . . , xn},
count the number of 3-tuples (xi, xj, xk) such that: 1.) i ≠j ≠ k
and, 2.) (xi, xj , xk) is legal. For example, for the numbers
{3, 5, 8, 4, 4}, (3, 4, 5) is a legal tuple while
(4, 4, 8) is not.
First, prove the correctness by using induction.
Second, your algorithm should run in O(n2 log(n)) time. Prove
the running time of your algorithm by using master theorem.
if a triangle can have sides of length x1, x2 and x3. Given a list
of n positive real numbers {x1, . . . , xn},
count the number of 3-tuples (xi, xj, xk) such that: 1.) i ≠j ≠ k
and, 2.) (xi, xj , xk) is legal. For example, for the numbers
{3, 5, 8, 4, 4}, (3, 4, 5) is a legal tuple while
(4, 4, 8) is not.
First, prove the correctness by using induction.
Second, your algorithm should run in O(n2 log(n)) time. Prove
the running time of your algorithm by using master theorem.