Number of triangles from a sorted sequence

Question

Given a strictly increasing sequence of n positive integers A(1) < A(2) < ... < A(n). We need to find the number of triangles with side lengths as 3 distinct elements of this sequence.

Since n <= 6000, checking every possible combination is not fast enough. Is there any better algorithm? Thanks for any help.

My pseudocode:

for i from 0 till n - 2
    for j from i+1 till n-1
        for k from j+1 till n
            if A[i] + A[j] > A[k] then count += 1
            else break

What is your actual algorithm? Can you give us an example? – Jean Jung Oct 29 '15 at 18:25 — Jean Jung, Oct 29 '15 at 18:25
I've added my psuedo-code in the post. – Artur Oct 29 '15 at 18:29 — Artur, Oct 29 '15 at 18:29

score 0 · Answer 1 · answered Oct 30 '15 at 08:45

0

You can exclude the third cycle and look for max k value with binary search. Complexity is O(N^2*Log(N)
You can reach better time - O(N^2) - just think how to use monotonicity property.

answered Oct 30 '15 at 08:45

MBo

77,366
5
53
86

Number of triangles from a sorted sequence

1 Answers1