finding triangulars from array

zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if and

A[P] + A[Q] > A[R], 
A[Q] + A[R] > A[P], 
A[R] + A[P] > A[Q]. 

For example, consider array A such that

A[0] = 10    A[1] = 2    A[2] =  5
A[3] =  1    A[4] = 8    A[5] = 20

Triplet (0, 2, 4) is triangular. Write a function

int triangle(const vector<int> &A);

that, given a zero-indexed array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

Assume that:

N is an integer within the range [0..100,000]; each element of array A is an integer within the range [-2,147,483,648..2,147,483,647]. For example, given array A such that

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20 the function should return 1, as explained above. Given array A such that A[0] = 10 A[1] = 50 A[2] = 5 A[3] = 1 the function should return 0. Expected wo开发者_开发技巧rst-case time complexity:

Expected worst-case space complexity: O(1)

First claim

First of all there is no point to take into account non-positive number. There's no chance you may achieve the triangle inequalities if at least one of the numbers is negative or zero. This is obvious, nevertheless here is the proof:

Assume A, B, C obey the triangle inequality, whereas C <= 0. Then you have

• A + C > B. Hence A > B.
• B + C > A. Hence B > A.

(contradiction).

Second claim

Suppose A, B, C obey the triangle inequalities, whereas C is the largest among A,B,C. Then for each A2 and B2 between A,B respectively and C - they will also obey triangle inequality.

In other words:

• A,B,C obey triangle inequalities.
• C >= A
• C >= B
• C >= A2 >= A
• C >= B2 >= B
• Then A2,B2,C also obey triangle inequalities.

The proof is trivial, enough to write the inequalities explicitly.

The consequence of this is that if C is the largest number for which you want to find the triangle inequality - you should check only two largest numbers from the set not exceeding C, and check if A + B > C.

Third claim

If 0 < A <= B <= C don't obey triangle inequalities, then C >= A*2.

The proof is trivial as well: A + B <= C, hence A + A <= C, hence C >= A*2

The algorithm

1. Pick 2 largest numbers B and C (B <= C).
2. Pick the largest number A not exceeding B, such that
   • A <= B <= C.
   • Make sure it's not the same element as B,C
   • Take into account only positive integers.
   • If unable to pick such a number - done. (No triangulars).
3. Check if A,B,C obey the triangle inequality. Test if A + B > C. (done if they do).
4. Discard the largest number C. Substitute C = B, then B = A.
5. Go to step 2.

Fourth claim

The above algorithm is logarithmic in the maximum integer size. In other words, its linear in the data type bitness. It's worst-case complexity is independent on the input length. Hence - it's O(1) in the input length.

Proof:

At every iteration (that does not find the solution) we have A <= C/2. After two such iterations A becomes the new C. This means that after every two iterations the largest number becomes at least 2 times smaller.

Obviously this gives us the upper bound of the number of the iterations. Gives our integers are limited by 31 bit (we ignore negatives), whereas the minimum interesting largest C is 1, this gives us no more that 2 * (31 - 1) = 60 iterations.

If O(N³) is acceptable time complexity then the Pseudocode below should work. If you have stricter time complexity requirements then you'll have to specify them.

for (P in A){
    for (Q in A){
        for (R in A){
            if(A[P] > 0 && A[Q] > 0 && A[R] > 0){
                if(A[P] > A[R] - A[Q] && A[Q] > A[P] - A[R] && A[R] > A[Q] - A[P]){
                    return 1;
                }
            }
        }
    }
}
return 0;

The reasoning behind the if statements is this:

Since the ints can be anything up to max int you have to deal with overflow. Adding them together could cause a weird error if there are two very large ints in the array. So instead we test if they are positive and then rewrite the formulae to do the same checks, but with subtraction. We don't need to do anything if any of the values are negative or 0, since:

Assume x <= 0
Assume x+y > z
Assume x+z > y
Then y > z and z > y which is a contradiction

So no negative or zero valued ints will be a part of a triple

Sorting would be very cool, but const vector and O(1) space requirements doesn't allow it.

(because this is homework) Some hint: triangular numbers are close to each other.

A hint: if you pick just two members of the array then what are the limits on the possible value of the third member of a triangular triplet? Any number outside those limits can be rejected immediately.

There are many in-place sorts; use one of them to sort the array - say comb sort for smaller ones (time complexity O(N^2)) or heap sort (complexity O(N log(N)).

Once you have sorted array, problem should be whether there is a set of 3 numbers where A[X] > (A[X-1] + A[X+1]) / 2 i.e. middle number is greater than average of preceding & succeeding numbers (sadly this is a guess, I don't have a real basis - if its incorrect I hope someone corrects me, but there should be some good way to redefine the 'triangle' requirement to be more easily checked).

Now you just have an O(1) iteration over the sorted array to check whether the condition is true, hence overall complexity will be that of the sorting algorithm (best case N logN)