Count triplets with sum smaller that a given value - GeeksforGeeks

Count triplets with sum smaller that a given value - GeeksforGeeks
Given an array of distinct integers and a sum value. Find count of triplets with sum smaller than given sum value. Expected Time Complexity is O(n²).

Input : arr[] = {-2, 0, 1, 3}
        sum = 2.
Output : 2
Explanation :  Below are triplets with sum less than 2
               (-2, 0, 1) and (-2, 0, 3) 

1) Sort the input array in increasing order.
2) Initialize result as 0.
3) Run a loop from i = 0 to n-2.  An iteration of this loop finds all
   triplets with arr[i] as first element.
     a) Initialize other two elements as corner elements of subarray
        arr[i+1..n-1], i.e., j = i+1 and k = n-1
     b) Move j and k toward each other until they meet, i.e., while (j < k)
            (i) if (arr[i] + arr[j] + arr[k] >= sum), then do k--

            // Else for current i and j, there can (k-j) possible third elements
            // that satisfy the constraint.
            (ii) Else Do ans += (k - j) followed by j++ 

int countTriplets(int arr[], int n, int sum)

{

    // Sort input array

    sort(arr, arr+n);

    // Initialize result

    int ans = 0;

    // Every iteration of loop counts triplet with

    // first element as arr[i].

    for (int i = 0; i < n - 2; i++)

    {

        // Initialize other two elements as corner elements

        // of subarray arr[j+1..k]

        int j = i + 1, k = n - 1;

        // Use Meet in the Middle concept

        while (j < k)

        {

            // If sum of current triplet is more or equal,

            // move right corner to look for smaller values

            if (arr[i] + arr[j] + arr[k] >= sum)

                k--;

            // Else move left corner

            else

            {

                // This is important. For current i and j, there

                // can be total k-j third elements.

                ans += (k - j);

                j++;

            }

        }

    }

    return ans;

}

O(N^3) A Simple Solution is to run three loops to consider all triplets one by one. For every triplet, compare the sums and increment count if triplet sum is smaller than given sum.

int countTriplets(int arr[], int n, int sum)

{

    // Initialize result

    int ans = 0;

    // Fix the first element as A[i]

    for (int i = 0; i < n-2; i++)

    {

       // Fix the second element as A[j]

       for (int j = i+1; j < n-1; j++)

       {

           // Now look for the third number

           for (int k = j+1; k < n; k++)

               if (arr[i] + arr[j] + arr[k] < sum)

                   ans++;

       }

    }

    return ans;

}

http://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/
Read full article from Count triplets with sum smaller that a given value - GeeksforGeeks