Lesson 13: CountTriangles (Count Triangles)

Lesson 13: CountTriangles

https://codility.com/programmers/lessons/13

First we sort the given array. 

If we search the triangles from this sorted array, we only have to check if A[P] + A[Q] > A[R], because it is always A[P] <= A[Q] <= A[R]. A[P] < A[Q] + A[R] and A[R] + A[P] > A[Q] are always hold.

We check P from the beginning. When we check P, first we set Q just to the next to P, and R to the next to Q. We can slide R while A[P] + A[Q] > A[R] is hold and every time we slide R, we can have (R - Q) combinations for (P, Q, R).　(Why? suppose you have a certain location of R, then Q can be any place between P and R, since Q is just getting larger and this does not invalidate A[P] + A[Q] > A[R]).

If we can not slide R anymore, then we slide Q to the next position. If it becomes Q==R, then slide R again.

This gives the 100% score as below.

int compare_int(const void *a, const void *b)
{
   //don't do 'return *(int*)a - *(int*)b;',
   //as this can cause underflow or overflow.

   if (*(int*)a == *(int*)b){
       return 0;
   }

   if (*(int*)a < *(int*)b){
       return -1;
   }
   
   return 1;
}

int solution(int A[], int N) 
{
    qsort(A, N, sizeof(int), compare_int);

    int cnt = 0;
    
    int p, q, r, ap, aq, ar;

    p = 0;
        
    for (   ; p <= N - 3; p++){
        ap = A[p];
        
        q = p + 1;
        r = p + 2;

        while (r < N){
            aq = A[q];
            ar = A[r];
            
            if (ap + aq > ar){
                cnt += r - q;
                r++;
            }
            else {
                q++;
                if (r == q){
                    r++;
                }
            }
        }

    }
    
    return cnt;
}