Wednesday, July 3, 2024
HomeLanguagesJavascriptJavascript Program to Count triplets with sum smaller than a ...

Javascript Program to Count triplets with sum smaller than a given value

Given an array of distinct integers and a sum value. Find count of triplets with sum smaller than given sum value. The expected Time Complexity is O(n2).
Examples: 
 

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) 

Input : arr[] = {5, 1, 3, 4, 7}
        sum = 12.
Output : 4
Explanation :  Below are triplets with sum less than 12
               (1, 3, 4), (1, 3, 5), (1, 3, 7) and 
               (1, 4, 5)

 

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 the triplet sum is smaller than the given sum. 
 

Javascript




<script>
// A Simple Javascript program to count triplets with sum smaller
// than a given value
    let arr = [5, 1, 3, 4, 7];
     
    function countTriplets(n,sum)
    {
     
        // Initialize result
        let ans = 0;
        
        // Fix the first element as A[i]
        for (let i = 0; i < n-2; i++)
        {
           // Fix the second element as A[j]
           for (let j = i + 1; j < n-1; j++)
           {
               // Now look for the third number
               for (let k = j + 1; k < n; k++)
                   if (arr[i] + arr[j] + arr[k] < sum)
                       ans++;
           }
        }
        return ans;
    }
     
    // Driver method to test the above function
    let sum = 12;
    document.write(countTriplets(arr.length, sum));
     
    // This code is contributed by avanitrachhadiya2155  
</script>


Output: 

4

Time Complexity: O(n3)

Auxiliary Space: O(1)

As constant extra space is used.

 An Efficient Solution can count triplets in O(n2) by sorting the array first, and then using method 1 of this post in a loop.
 

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= sum
                then 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++ 

Below is the implementation of the above idea. 
 

Javascript




<script>
// A Simple Javascript program to count triplets with sum smaller
// than a given value
    let arr = [5, 1, 3, 4, 7];
     
    function countTriplets(n,sum)
    {
     
        // Sort input array
        arr.sort(function(a,b){return b-a});
         
        // Initialize result
        let ans = 0;
         
        // Every iteration of loop counts triplet with
        // first element as arr[i].
        for (let i = 0; i < n - 2; i++)
        {
         
            // Initialize other two elements as corner elements
            // of subarray arr[j+1..k]
            let 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;
    }
     
    // Driver method to test the above function
    let sum = 12;
    document.write(countTriplets(arr.length, sum));
     
    // This code is contributed by rag2127
</script>


Output: 

4

Time Complexity: O(n2)

Auxiliary Space: O(1)

As constant extra space is used.

Please refer complete article on Count triplets with sum smaller than a given value for more details!

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Shaida Kate Naidoo
am passionate about learning the latest technologies available to developers in either a Front End or Back End capacity. I enjoy creating applications that are well designed and responsive, in addition to being user friendly. I thrive in fast paced environments. With a diverse educational and work experience background, I excel at collaborating with teams both local and international. A versatile developer with interests in Software Development and Software Engineering. I consider myself to be adaptable and a self motivated learner. I am interested in new programming technologies, and continuous self improvement.
RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments