The numbers in the array contain the sides of a real triangle

Question

Check if the array of integers n 3 contains numbers that can form a triangle (i.e. the sum of either of the two numbers is greater than the third).

Apparently, this can be done in O(n) time.

(the obvious solution to O(n log n) is to sort the array, please don't do this)

Answer 1

It is hard to imagine N numbers (where N is moderately large), so there is no triangle triangle. But we will try:

Consider a growing sequence, where each next value is at the limit of N[i] = N[i-1] + N[i-2] . This is nothing more than a Fibonacci sequence. Approximately this can be considered as a geometric progression with a golden ratio (GRf ~ = 1.618).
You can see that if N_largest < N_smallest * (GRf**(N-1)) , then there will necessarily be a triangle triangle. This definition is pretty fuzzy because of the floating point compared to the integer and because of GRf, which is the limit, not the actual geometric factor. In any case, a carefully implemented program will give an O (n) test that can check if it has a triple. If not, then we need to perform some other tests (still thinking).

EDIT . The direct conclusion from the Fibonacci idea is that for integer input (as indicated in Q) there will be a guaranteed solution for any possible input if the size of the array is larger than log_GRf(MAX_INT) , which is 47 for 32 bits or 93 for 64 bit. In fact, we can use the largest value from the input array to determine it better.

This gives us the following algorithm:

Step 1) Find MAX_VAL from the input: O(n)

Step 2) Calculate the minimum size of the array, which would guarantee the existence of a solution:
N_LIMIT = log_base_GRf(MAX_VAL) : O(1)

Step 3.1) if N> N_LIMIT: return true : O(1)

Step 3.2) else sort and use the direct method O(n*log(n))

Since for large values ​​of N (and this is the only case where complexity occurs), this is O(n) (or even O(1) in cases where N > log_base_GRf(MAX_INT) ), we can say this is O(n) .