Codility - CountTriangles  

by ne on 2022-08-27 under Algo/DS/Problems tagged with codility

The problem belongs to Codility, here is the link to the problem

Following code segment contains the description in the class comments, followed by fully working solution

 

 



/**
 * A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The slice consists of the elements A[P], A[P + 1], ..., A[Q]. A distinct slice is a slice consisting of only unique numbers. That is, no individual number occurs more than once in the slice.
 *
 * For example, consider integer M = 6 and array A such that:
 *
 *     A[0] = 3
 *     A[1] = 4
 *     A[2] = 5
 *     A[3] = 5
 *     A[4] = 2
 * There are exactly nine distinct slices: (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (3, 3), (3, 4) and (4, 4).
 *
 * The goal is to calculate the number of distinct slices.
 */

public int solution(int[] A) {
        Arrays.sort(A);
        int tr=0;
        for(int p=0;p < A.length-2;p++){
            int q=p+1;
            int r=p+2;
            while(r < A.length){
                if(A[p]+A[q] > A[r]){
                    // if it works for p,q and r.. then it should work for all q's in between q and r.. hence r-q
                    tr+=(r-q);
                    r++;
                }else if (q < r-1){
                    // ELSE of the condition.. meaning it didn't work for R, now start incrementing Q for this new R.
                    q++;
                }else{
                    // Q==R-1 , and p,q,r doesn't work.. try moving both q and r now.. or else P itself in the for then
                    r++;
                    q++;
                }
            }
        }
        return tr;
    }