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.
Python 3
# A Simple Python 3 program to count triplets with sum smaller# than a given valuedef countTriplets(arr, n, sum): # Initialize result ans = 0 # Fix the first element as A[i] for i in range( 0 ,n-2): # Fix the second element as A[j] for j in range( i+1 ,n-1): # Now look for the third number for k in range( j+1, n): if (arr[i] + arr[j] + arr[k] < sum): ans+=1 return ans# Driver programarr = [5, 1, 3, 4, 7]n = len(arr)sum = 12print(countTriplets(arr, n, sum))#Contributed by Smitha |
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.
Python3
# Python3 program to count triplets with # sum smaller than a given value # Function to count triplets with sum smaller# than a given value def countTriplets(arr,n,sum): # Sort input array arr.sort() # Initialize result ans = 0 # Every iteration of loop counts triplet with # first element as arr[i]. for i in range(0,n-2): # Initialize other two elements as corner elements # of subarray arr[j+1..k] 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 = k-1 # 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 = j+1 return ans# Driver program if __name__=='__main__': arr = [5, 1, 3, 4, 7] n = len(arr) sum = 12 print(countTriplets(arr, n, sum)) # This code is contributed by # Yatin Gupta |
Output:
4
Time Complexity: O(n3)
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!
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
