Problem
Given a list of numbers, count the number of triplets having a sum less than a given target.
Example One
{
"target": 4,
"numbers": [5, 0, -1, 3, 2]
}
Output:
2
{numbers[1], numbers[2], numbers[3]} and {numbers[1], numbers[2], numbers[4]} are the triplets having sum less than 4.
Example Two
{
"target": 7,
"numbers": [2, 2, 2, 1]
}
Output:
4
{numbers[0], numbers[1], numbers[2]}, {numbers[0], numbers[1], numbers[3]}, {numbers[0], numbers[2], numbers[3]} and {numbers[1], numbers[2], numbers[3]} are the triplets having sum less than 7.
Solution
function count_triplets(target, numbers) {
// Write your code here.
// Initialize result
let n = numbers.length;
let result = 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 (numbers[i] + numbers[j] + numbers[k] < target)
result++;
}
}
return result;
}
Time and Space Complexity
Time: O(n * n).
Auxiliary space: O(1).
Total space: O(n)
Tech Corner 