Find all triplets which sum less than given value x
Finding all possible triplets in an array whose sum is less
than a given value x
. A triplet refers to a group of three elements in the array, and the task is to
identify those triplets whose sum is less than the specified value x
.
For instance, given an array [8, 2, 0, 6, -2, 6, -1, 9, 4, 3]
and x = 3
, we need to find
and display all triplets whose sum is less than 3.
Problem Statement
The problem requires identifying and displaying all possible triplets from an array whose sum is less than a given
value x
.
Explanation with Example
Let's consider the example provided: array [8, 2, 0, 6, -2, 6, -1, 9, 4, 3]
and x = 3
.
We need to find and display all triplets whose sum is less than 3:
(2 + 0 + -2) = 0
(2 + 0 + -1) = 1
(2 + -2 + -1) = -1
(0 + -2 + -1) = -3
(0 + -2 + 4) = 2
(0 + -2 + 3) = 1
(0 + -1 + 3) = 2
(-2 + -1 + 4) = 1
(-2 + -1 + 3) = 0
Idea to Solve the Problem
To solve this problem, we can follow these steps:
- Iterate through the array using three nested loops, each representing a possible element for the triplet.
- Check if the sum of the current triplet is less than the given value
x
. - If the condition is met, display the triplet.
Pseudocode
Function display(arr, size):
Loop i from 0 to size - 1:
Print arr[i] and a space
Function tripletsWithLessThanX(arr, size, x):
If size is less than 3:
Return
Display "Array:"
Display array elements using display function
Display "Given x:", x
status = 0
Loop i from 0 to size - 3:
Loop j from i + 1 to size - 2:
Loop k from j + 1 to size - 1:
If arr[i] + arr[j] + arr[k] < x:
Display the triplet and its sum
Set status to 1
If status is 0:
Display "None"
Main:
Define array elements
size = size of array
x = value of x
Call tripletsWithLessThanX(arr, size, x)
Algorithm Explanation
- The
tripletsWithLessThanX
function iterates through the array using three nested loops to cover all possible triplets. - If the sum of the current triplet is less than
x
, the function displays the triplet and updates the status variable. - If no valid triplets are found, the function displays "None".
Code Solution
// C Program
// Find all triplets which sum less than given value x
#include <stdio.h>
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", arr[i]);
}
}
// Find all triplets which sum less than x
void tripletsWithLessThanX(int arr[], int size, int x)
{
if (size < 3)
{
return;
}
printf(" Array : ");
//Display array elements
display(arr, size);
printf("\n Given x : %d", x);
// Result indicator
int status = 0;
// Loop which is iterate the first element of result
for (int i = 0; i < size - 2; ++i)
{
// Loop which is iterate the second element of result
for (int j = i + 1; j < size - 1; ++j)
{
// Loop which is iterate the third element of result
for (int k = j + 1; k < size; ++k)
{
// Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] < x)
{
status = 1;
// Display three elements
printf("\n (%d + %d + %d) = %d",
arr[i], arr[j], arr[k],
(arr[i] + arr[j] + arr[k]));
}
}
}
}
if (status == 0)
{
printf(" \n None\n");
}
printf("\n");
}
int main()
{
//Define array elements
int arr1[] = {
8 , 2 , 0 , 6 , -2 , 6 , -1 , 9 , 4 , 3
};
// Define array elements
int arr2[] = {
9 , 2 , -7 , 4 , 1 , 3 , 0 , 7 , 22 , 8 , -4
};
// Test A
int size = sizeof(arr1) / sizeof(arr1[0]);
tripletsWithLessThanX(arr1, size, 3);
tripletsWithLessThanX(arr1, size, -6);
// Test B
size = sizeof(arr2) / sizeof(arr2[0]);
tripletsWithLessThanX(arr2, size, -2);
return 0;
}
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
(2 + 0 + -2) = 0
(2 + 0 + -1) = 1
(2 + -2 + -1) = -1
(0 + -2 + -1) = -3
(0 + -2 + 4) = 2
(0 + -2 + 3) = 1
(0 + -1 + 3) = 2
(-2 + -1 + 4) = 1
(-2 + -1 + 3) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
(2 + -7 + 1) = -4
(2 + -7 + 0) = -5
(2 + -7 + -4) = -9
(-7 + 4 + 0) = -3
(-7 + 4 + -4) = -7
(-7 + 1 + 3) = -3
(-7 + 1 + 0) = -6
(-7 + 1 + -4) = -10
(-7 + 3 + 0) = -4
(-7 + 3 + -4) = -8
(-7 + 0 + -4) = -11
(-7 + 7 + -4) = -4
(-7 + 8 + -4) = -3
(1 + 0 + -4) = -3
/*
Java Program for
Find all triplets which sum less than given value x
*/
public class Triplets
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
}
// Find all triplets which sum less than x
public void tripletsWithLessThanX(int[] arr, int size, int x)
{
if (size < 3)
{
return;
}
System.out.print("\n Array : ");
//Display array elements
display(arr, size);
System.out.print("\n Given x : " + x);
// Result indicator
boolean status = false;
// Loop which is iterate the first element of result
for (int i = 0; i < size - 2; ++i)
{
// Loop which is iterate the second element of result
for (int j = i + 1; j < size - 1; ++j)
{
// Loop which is iterate the third element of result
for (int k = j + 1; k < size; ++k)
{
// Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] < x)
{
status = true;
// Display three elements
System.out.print("\n (" +
arr[i] + " + " +
arr[j] + " + " +
arr[k] + ") = " +
(arr[i] + arr[j] + arr[k]));
}
}
}
}
if (status == false)
{
System.out.print(" \n None\n");
}
}
public static void main(String[] args)
{
Triplets task = new Triplets();
// Define array elements
int[] arr1 = {
8 , 2 , 0 , 6 , -2 , 6 , -1 , 9 , 4 , 3
};
// Define array elements
int[] arr2 = {
9 , 2 , -7 , 4 , 1 , 3 , 0 , 7 , 22 , 8 , -4
};
// Test A
int size = arr1.length;
task.tripletsWithLessThanX(arr1, size, 3);
task.tripletsWithLessThanX(arr1, size, -6);
// Test B
size = arr2.length;
task.tripletsWithLessThanX(arr2, size, -2);
}
}
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
(2 + 0 + -2) = 0
(2 + 0 + -1) = 1
(2 + -2 + -1) = -1
(0 + -2 + -1) = -3
(0 + -2 + 4) = 2
(0 + -2 + 3) = 1
(0 + -1 + 3) = 2
(-2 + -1 + 4) = 1
(-2 + -1 + 3) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
(2 + -7 + 1) = -4
(2 + -7 + 0) = -5
(2 + -7 + -4) = -9
(-7 + 4 + 0) = -3
(-7 + 4 + -4) = -7
(-7 + 1 + 3) = -3
(-7 + 1 + 0) = -6
(-7 + 1 + -4) = -10
(-7 + 3 + 0) = -4
(-7 + 3 + -4) = -8
(-7 + 0 + -4) = -11
(-7 + 7 + -4) = -4
(-7 + 8 + -4) = -3
(1 + 0 + -4) = -3
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Find all triplets which sum less than given value x
*/
class Triplets
{
public:
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
}
// Find all triplets which sum less than x
void tripletsWithLessThanX(int arr[], int size, int x)
{
if (size < 3)
{
return;
}
cout << "\n Array : ";
//Display array elements
this->display(arr, size);
cout << "\n Given x : " << x;
// Result indicator
bool status = false;
// Loop which is iterate the first element of result
for (int i = 0; i < size - 2; ++i)
{
// Loop which is iterate the second element of result
for (int j = i + 1; j < size - 1; ++j)
{
// Loop which is iterate the third element of result
for (int k = j + 1; k < size; ++k)
{
// Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] < x)
{
status = true;
// Display three elements
cout << "\n (" << arr[i]
<< " + " << arr[j] << " + "
<< arr[k] << ") = "
<< (arr[i] + arr[j] + arr[k]);
}
}
}
}
if (status == false)
{
cout << " \n None\n";
}
}
};
int main()
{
Triplets *task = new Triplets();
// Define array elements
int arr1[] = {
8 , 2 , 0 , 6 , -2 , 6 , -1 , 9 , 4 , 3
};
// Define array elements
int arr2[] = {
9 , 2 , -7 , 4 , 1 , 3 , 0 , 7 , 22 , 8 , -4
};
// Test A
int size = sizeof(arr1) / sizeof(arr1[0]);
task->tripletsWithLessThanX(arr1, size, 3);
task->tripletsWithLessThanX(arr1, size, -6);
// Test B
size = sizeof(arr2) / sizeof(arr2[0]);
task->tripletsWithLessThanX(arr2, size, -2);
return 0;
}
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
(2 + 0 + -2) = 0
(2 + 0 + -1) = 1
(2 + -2 + -1) = -1
(0 + -2 + -1) = -3
(0 + -2 + 4) = 2
(0 + -2 + 3) = 1
(0 + -1 + 3) = 2
(-2 + -1 + 4) = 1
(-2 + -1 + 3) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
(2 + -7 + 1) = -4
(2 + -7 + 0) = -5
(2 + -7 + -4) = -9
(-7 + 4 + 0) = -3
(-7 + 4 + -4) = -7
(-7 + 1 + 3) = -3
(-7 + 1 + 0) = -6
(-7 + 1 + -4) = -10
(-7 + 3 + 0) = -4
(-7 + 3 + -4) = -8
(-7 + 0 + -4) = -11
(-7 + 7 + -4) = -4
(-7 + 8 + -4) = -3
(1 + 0 + -4) = -3
// Include namespace system
using System;
/*
Csharp Program for
Find all triplets which sum less than given value x
*/
public class Triplets
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
}
// Find all triplets which sum less than x
public void tripletsWithLessThanX(int[] arr, int size, int x)
{
if (size < 3)
{
return;
}
Console.Write("\n Array : ");
//Display array elements
this.display(arr, size);
Console.Write("\n Given x : " + x);
// Result indicator
Boolean status = false;
// Loop which is iterate the first element of result
for (int i = 0; i < size - 2; ++i)
{
// Loop which is iterate the second element of result
for (int j = i + 1; j < size - 1; ++j)
{
// Loop which is iterate the third element of result
for (int k = j + 1; k < size; ++k)
{
// Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] < x)
{
status = true;
// Display three elements
Console.Write("\n (" +
arr[i] + " + " +
arr[j] + " + " +
arr[k] + ") = " +
(arr[i] + arr[j] + arr[k]));
}
}
}
}
if (status == false)
{
Console.Write(" \n None\n");
}
}
public static void Main(String[] args)
{
Triplets task = new Triplets();
// Define array elements
int[] arr1 = {
8 , 2 , 0 , 6 , -2 , 6 , -1 , 9 , 4 , 3
};
// Define array elements
int[] arr2 = {
9 , 2 , -7 , 4 , 1 , 3 , 0 , 7 , 22 , 8 , -4
};
// Test A
int size = arr1.Length;
task.tripletsWithLessThanX(arr1, size, 3);
task.tripletsWithLessThanX(arr1, size, -6);
// Test B
size = arr2.Length;
task.tripletsWithLessThanX(arr2, size, -2);
}
}
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
(2 + 0 + -2) = 0
(2 + 0 + -1) = 1
(2 + -2 + -1) = -1
(0 + -2 + -1) = -3
(0 + -2 + 4) = 2
(0 + -2 + 3) = 1
(0 + -1 + 3) = 2
(-2 + -1 + 4) = 1
(-2 + -1 + 3) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
(2 + -7 + 1) = -4
(2 + -7 + 0) = -5
(2 + -7 + -4) = -9
(-7 + 4 + 0) = -3
(-7 + 4 + -4) = -7
(-7 + 1 + 3) = -3
(-7 + 1 + 0) = -6
(-7 + 1 + -4) = -10
(-7 + 3 + 0) = -4
(-7 + 3 + -4) = -8
(-7 + 0 + -4) = -11
(-7 + 7 + -4) = -4
(-7 + 8 + -4) = -3
(1 + 0 + -4) = -3
package main
import "fmt"
/*
Go Program for
Find all triplets which sum less than given value x
*/
//Function which is display array elements
func display(arr[] int, size int) {
for i := 0 ; i < size ; i++ {
fmt.Print(" ", arr[i])
}
}
// Find all triplets which sum less than x
func tripletsWithLessThanX(arr[] int, size int, x int) {
if size < 3 {
return
}
fmt.Print("\n Array : ")
//Display array elements
display(arr, size)
fmt.Print("\n Given x : ", x)
// Result indicator
var status bool = false
// Loop which is iterate the first element of result
for i := 0 ; i < size - 2 ; i++ {
// Loop which is iterate the second element of result
for j := i + 1 ; j < size - 1 ; j++ {
// Loop which is iterate the third element of result
for k := j + 1 ; k < size ; k++ {
// Check if whether resultant sum is to zero or not
if arr[i] + arr[j] + arr[k] < x {
status = true
// Display three elements
fmt.Print("\n (", arr[i], " + ",
arr[j], " + ", arr[k], ") = ",
(arr[i] + arr[j] + arr[k]))
}
}
}
}
if status == false {
fmt.Print(" \n None\n")
}
}
func main() {
// Define array elements
var arr1 = [] int {8 , 2 , 0 , 6 , -2 , 6 , -1 , 9 , 4 , 3}
// Define array elements
var arr2 = [] int {9 , 2 , -7 , 4 , 1 , 3 , 0 , 7 , 22 , 8 , -4}
// Test A
var size int = len(arr1)
tripletsWithLessThanX(arr1, size, 3)
tripletsWithLessThanX(arr1, size, -6)
// Test B
size = len(arr2)
tripletsWithLessThanX(arr2, size, -2)
}
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
(2 + 0 + -2) = 0
(2 + 0 + -1) = 1
(2 + -2 + -1) = -1
(0 + -2 + -1) = -3
(0 + -2 + 4) = 2
(0 + -2 + 3) = 1
(0 + -1 + 3) = 2
(-2 + -1 + 4) = 1
(-2 + -1 + 3) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
(2 + -7 + 1) = -4
(2 + -7 + 0) = -5
(2 + -7 + -4) = -9
(-7 + 4 + 0) = -3
(-7 + 4 + -4) = -7
(-7 + 1 + 3) = -3
(-7 + 1 + 0) = -6
(-7 + 1 + -4) = -10
(-7 + 3 + 0) = -4
(-7 + 3 + -4) = -8
(-7 + 0 + -4) = -11
(-7 + 7 + -4) = -4
(-7 + 8 + -4) = -3
(1 + 0 + -4) = -3
<?php
/*
Php Program for
Find all triplets which sum less than given value x
*/
class Triplets
{
//Function which is display array elements
public function display($arr, $size)
{
for ($i = 0; $i < $size; ++$i)
{
echo(" ".$arr[$i]);
}
}
// Find all triplets which sum less than x
public function tripletsWithLessThanX($arr, $size, $x)
{
if ($size < 3)
{
return;
}
echo("\n Array : ");
//Display array elements
$this->display($arr, $size);
echo("\n Given x : ".$x);
// Result indicator
$status = false;
// Loop which is iterate the first element of result
for ($i = 0; $i < $size - 2; ++$i)
{
// Loop which is iterate the second element of result
for ($j = $i + 1; $j < $size - 1; ++$j)
{
// Loop which is iterate the third element of result
for ($k = $j + 1; $k < $size; ++$k)
{
// Check if whether resultant sum is to zero or not
if ($arr[$i] + $arr[$j] + $arr[$k] < $x)
{
$status = true;
// Display three elements
echo("\n (".$arr[$i].
" + ".$arr[$j].
" + ".$arr[$k].
") = ".($arr[$i] + $arr[$j] + $arr[$k]));
}
}
}
}
if ($status == false)
{
echo(" \n None\n");
}
}
}
function main()
{
$task = new Triplets();
// Define array elements
$arr1 = array(8, 2, 0, 6, -2, 6, -1, 9, 4, 3);
// Define array elements
$arr2 = array(9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4);
// Test A
$size = count($arr1);
$task->tripletsWithLessThanX($arr1, $size, 3);
$task->tripletsWithLessThanX($arr1, $size, -6);
// Test B
$size = count($arr2);
$task->tripletsWithLessThanX($arr2, $size, -2);
}
main();
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
(2 + 0 + -2) = 0
(2 + 0 + -1) = 1
(2 + -2 + -1) = -1
(0 + -2 + -1) = -3
(0 + -2 + 4) = 2
(0 + -2 + 3) = 1
(0 + -1 + 3) = 2
(-2 + -1 + 4) = 1
(-2 + -1 + 3) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
(2 + -7 + 1) = -4
(2 + -7 + 0) = -5
(2 + -7 + -4) = -9
(-7 + 4 + 0) = -3
(-7 + 4 + -4) = -7
(-7 + 1 + 3) = -3
(-7 + 1 + 0) = -6
(-7 + 1 + -4) = -10
(-7 + 3 + 0) = -4
(-7 + 3 + -4) = -8
(-7 + 0 + -4) = -11
(-7 + 7 + -4) = -4
(-7 + 8 + -4) = -3
(1 + 0 + -4) = -3
/*
Node JS Program for
Find all triplets which sum less than given value x
*/
class Triplets
{
//Function which is display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
}
// Find all triplets which sum less than x
tripletsWithLessThanX(arr, size, x)
{
if (size < 3)
{
return;
}
process.stdout.write("\n Array : ");
//Display array elements
this.display(arr, size);
process.stdout.write("\n Given x : " + x);
// Result indicator
var status = false;
// Loop which is iterate the first element of result
for (var i = 0; i < size - 2; ++i)
{
// Loop which is iterate the second element of result
for (var j = i + 1; j < size - 1; ++j)
{
// Loop which is iterate the third element of result
for (var k = j + 1; k < size; ++k)
{
// Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] < x)
{
status = true;
// Display three elements
process.stdout.write("\n (" +
arr[i] + " + " +
arr[j] + " + " +
arr[k] + ") = " +
(arr[i] + arr[j] + arr[k]));
}
}
}
}
if (status == false)
{
process.stdout.write(" \n None\n");
}
}
}
function main()
{
var task = new Triplets();
// Define array elements
var arr1 = [8, 2, 0, 6, -2, 6, -1, 9, 4, 3];
// Define array elements
var arr2 = [9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4];
// Test A
var size = arr1.length;
task.tripletsWithLessThanX(arr1, size, 3);
task.tripletsWithLessThanX(arr1, size, -6);
// Test B
size = arr2.length;
task.tripletsWithLessThanX(arr2, size, -2);
}
main();
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
(2 + 0 + -2) = 0
(2 + 0 + -1) = 1
(2 + -2 + -1) = -1
(0 + -2 + -1) = -3
(0 + -2 + 4) = 2
(0 + -2 + 3) = 1
(0 + -1 + 3) = 2
(-2 + -1 + 4) = 1
(-2 + -1 + 3) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
(2 + -7 + 1) = -4
(2 + -7 + 0) = -5
(2 + -7 + -4) = -9
(-7 + 4 + 0) = -3
(-7 + 4 + -4) = -7
(-7 + 1 + 3) = -3
(-7 + 1 + 0) = -6
(-7 + 1 + -4) = -10
(-7 + 3 + 0) = -4
(-7 + 3 + -4) = -8
(-7 + 0 + -4) = -11
(-7 + 7 + -4) = -4
(-7 + 8 + -4) = -3
(1 + 0 + -4) = -3
# Python 3 Program for
# Find all triplets which sum less than given value x
class Triplets :
# Function which is display list elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
# Find all triplets which sum less than x
def tripletsWithLessThanX(self, arr, size, x) :
if (size < 3) :
return
print("\n Array : ", end = "")
# Display list elements
self.display(arr, size)
print("\n Given x : ", x, end = "")
# Result indicator
status = False
i = 0
# Loop which is iterate the first element of result
while (i < size - 2) :
j = i + 1
# Loop which is iterate the second element of result
while (j < size - 1) :
k = j + 1
# Loop which is iterate the third element of result
while (k < size) :
# Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] < x) :
status = True
# Display three elements
print("\n (", arr[i] ," + ",
arr[j] ," + ", arr[k] ,") = ",
(arr[i] + arr[j] + arr[k]), end = "")
k += 1
j += 1
i += 1
if (status == False) :
print(" \n None")
def main() :
task = Triplets()
# Define list elements
arr1 = [8, 2, 0, 6, -2, 6, -1, 9, 4, 3]
# Define list elements
arr2 = [9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4]
# Test A
size = len(arr1)
task.tripletsWithLessThanX(arr1, size, 3)
task.tripletsWithLessThanX(arr1, size, -6)
# Test B
size = len(arr2)
task.tripletsWithLessThanX(arr2, size, -2)
if __name__ == "__main__": main()
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
( 2 + 0 + -2 ) = 0
( 2 + 0 + -1 ) = 1
( 2 + -2 + -1 ) = -1
( 0 + -2 + -1 ) = -3
( 0 + -2 + 4 ) = 2
( 0 + -2 + 3 ) = 1
( 0 + -1 + 3 ) = 2
( -2 + -1 + 4 ) = 1
( -2 + -1 + 3 ) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
( 2 + -7 + 1 ) = -4
( 2 + -7 + 0 ) = -5
( 2 + -7 + -4 ) = -9
( -7 + 4 + 0 ) = -3
( -7 + 4 + -4 ) = -7
( -7 + 1 + 3 ) = -3
( -7 + 1 + 0 ) = -6
( -7 + 1 + -4 ) = -10
( -7 + 3 + 0 ) = -4
( -7 + 3 + -4 ) = -8
( -7 + 0 + -4 ) = -11
( -7 + 7 + -4 ) = -4
( -7 + 8 + -4 ) = -3
( 1 + 0 + -4 ) = -3
# Ruby Program for
# Find all triplets which sum less than given value x
class Triplets
# Function which is display array elements
def display(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
end
# Find all triplets which sum less than x
def tripletsWithLessThanX(arr, size, x)
if (size < 3)
return
end
print("\n Array : ")
# Display array elements
self.display(arr, size)
print("\n Given x : ", x)
# Result indicator
status = false
i = 0
# Loop which is iterate the first element of result
while (i < size - 2)
j = i + 1
# Loop which is iterate the second element of result
while (j < size - 1)
k = j + 1
# Loop which is iterate the third element of result
while (k < size)
# Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] < x)
status = true
# Display three elements
print("\n (",
arr[i] ," + ",
arr[j] ," + ",
arr[k] ,") = ",
(arr[i] + arr[j] + arr[k]))
end
k += 1
end
j += 1
end
i += 1
end
if (status == false)
print(" \n None\n")
end
end
end
def main()
task = Triplets.new()
# Define array elements
arr1 = [8, 2, 0, 6, -2, 6, -1, 9, 4, 3]
# Define array elements
arr2 = [9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4]
# Test A
size = arr1.length
task.tripletsWithLessThanX(arr1, size, 3)
task.tripletsWithLessThanX(arr1, size, -6)
# Test B
size = arr2.length
task.tripletsWithLessThanX(arr2, size, -2)
end
main()
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
(2 + 0 + -2) = 0
(2 + 0 + -1) = 1
(2 + -2 + -1) = -1
(0 + -2 + -1) = -3
(0 + -2 + 4) = 2
(0 + -2 + 3) = 1
(0 + -1 + 3) = 2
(-2 + -1 + 4) = 1
(-2 + -1 + 3) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
(2 + -7 + 1) = -4
(2 + -7 + 0) = -5
(2 + -7 + -4) = -9
(-7 + 4 + 0) = -3
(-7 + 4 + -4) = -7
(-7 + 1 + 3) = -3
(-7 + 1 + 0) = -6
(-7 + 1 + -4) = -10
(-7 + 3 + 0) = -4
(-7 + 3 + -4) = -8
(-7 + 0 + -4) = -11
(-7 + 7 + -4) = -4
(-7 + 8 + -4) = -3
(1 + 0 + -4) = -3
/*
Scala Program for
Find all triplets which sum less than given value x
*/
class Triplets()
{
//Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
}
// Find all triplets which sum less than x
def tripletsWithLessThanX(arr: Array[Int], size: Int, x: Int): Unit = {
if (size < 3)
{
return;
}
print("\n Array : ");
//Display array elements
display(arr, size);
print("\n Given x : " + x);
// Result indicator
var status: Boolean = false;
var i: Int = 0;
// Loop which is iterate the first element of result
while (i < size - 2)
{
var j: Int = i + 1;
// Loop which is iterate the second element of result
while (j < size - 1)
{
var k: Int = j + 1;
// Loop which is iterate the third element of result
while (k < size)
{
// Check if whether resultant sum is to zero or not
if (arr(i) + arr(j) + arr(k) < x)
{
status = true;
// Display three elements
print("\n (" + arr(i) + " + " +
arr(j) + " + " + arr(k) + ") = " +
(arr(i) + arr(j) + arr(k)));
}
k += 1;
}
j += 1;
}
i += 1;
}
if (status == false)
{
print(" \n None\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Triplets = new Triplets();
// Define array elements
var arr1: Array[Int] = Array(8, 2, 0, 6, -2, 6, -1, 9, 4, 3);
// Define array elements
var arr2: Array[Int] = Array(9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4);
// Test A
var size: Int = arr1.length;
task.tripletsWithLessThanX(arr1, size, 3);
task.tripletsWithLessThanX(arr1, size, -6);
// Test B
size = arr2.length;
task.tripletsWithLessThanX(arr2, size, -2);
}
}
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
(2 + 0 + -2) = 0
(2 + 0 + -1) = 1
(2 + -2 + -1) = -1
(0 + -2 + -1) = -3
(0 + -2 + 4) = 2
(0 + -2 + 3) = 1
(0 + -1 + 3) = 2
(-2 + -1 + 4) = 1
(-2 + -1 + 3) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
(2 + -7 + 1) = -4
(2 + -7 + 0) = -5
(2 + -7 + -4) = -9
(-7 + 4 + 0) = -3
(-7 + 4 + -4) = -7
(-7 + 1 + 3) = -3
(-7 + 1 + 0) = -6
(-7 + 1 + -4) = -10
(-7 + 3 + 0) = -4
(-7 + 3 + -4) = -8
(-7 + 0 + -4) = -11
(-7 + 7 + -4) = -4
(-7 + 8 + -4) = -3
(1 + 0 + -4) = -3
import Foundation;
/*
Swift 4 Program for
Find all triplets which sum less than given value x
*/
class Triplets
{
//Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
}
// Find all triplets which sum less than x
func tripletsWithLessThanX(_ arr: [Int], _ size: Int, _ x: Int)
{
if (size < 3)
{
return;
}
print("\n Array : ", terminator: "");
//Display array elements
self.display(arr, size);
print("\n Given x : ", x, terminator: "");
// Result indicator
var status: Bool = false;
var i: Int = 0;
// Loop which is iterate the first element of result
while (i < size - 2)
{
var j: Int = i + 1;
// Loop which is iterate the second element of result
while (j < size - 1)
{
var k: Int = j + 1;
// Loop which is iterate the third element of result
while (k < size)
{
// Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] < x)
{
status = true;
// Display three elements
print("\n (", arr[i] ,"+",
arr[j] ,"+", arr[k] ,") = ",
(arr[i] + arr[j] + arr[k]), terminator: "");
}
k += 1;
}
j += 1;
}
i += 1;
}
if (status == false)
{
print(" \n None");
}
}
}
func main()
{
let task: Triplets = Triplets();
// Define array elements
let arr1: [Int] = [8, 2, 0, 6, -2, 6, -1, 9, 4, 3];
// Define array elements
let arr2: [Int] = [9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4];
// Test A
var size: Int = arr1.count;
task.tripletsWithLessThanX(arr1, size, 3);
task.tripletsWithLessThanX(arr1, size, -6);
// Test B
size = arr2.count;
task.tripletsWithLessThanX(arr2, size, -2);
}
main();
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
( 2 + 0 + -2 ) = 0
( 2 + 0 + -1 ) = 1
( 2 + -2 + -1 ) = -1
( 0 + -2 + -1 ) = -3
( 0 + -2 + 4 ) = 2
( 0 + -2 + 3 ) = 1
( 0 + -1 + 3 ) = 2
( -2 + -1 + 4 ) = 1
( -2 + -1 + 3 ) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
( 2 + -7 + 1 ) = -4
( 2 + -7 + 0 ) = -5
( 2 + -7 + -4 ) = -9
( -7 + 4 + 0 ) = -3
( -7 + 4 + -4 ) = -7
( -7 + 1 + 3 ) = -3
( -7 + 1 + 0 ) = -6
( -7 + 1 + -4 ) = -10
( -7 + 3 + 0 ) = -4
( -7 + 3 + -4 ) = -8
( -7 + 0 + -4 ) = -11
( -7 + 7 + -4 ) = -4
( -7 + 8 + -4 ) = -3
( 1 + 0 + -4 ) = -3
/*
Kotlin Program for
Find all triplets which sum less than given value x
*/
class Triplets
{
//Function which is display array elements
fun display(arr: Array < Int > , size: Int): Unit
{
var i: Int = 0;
while (i < size)
{
print(" " + arr[i]);
i += 1;
}
}
// Find all triplets which sum less than x
fun tripletsWithLessThanX(arr: Array < Int > , size: Int, x: Int): Unit
{
if (size < 3)
{
return;
}
print("\n Array : ");
//Display array elements
this.display(arr, size);
print("\n Given x : " + x);
// Result indicator
var status: Boolean = false;
var i: Int = 0;
// Loop which is iterate the first element of result
while (i < size - 2)
{
var j: Int = i + 1;
// Loop which is iterate the second element of result
while (j < size - 1)
{
var k: Int = j + 1;
// Loop which is iterate the third element of result
while (k < size)
{
// Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] < x)
{
status = true;
// Display three elements
print("\n (" + arr[i] + " + " +
arr[j] + " + " + arr[k] + ") = " +
(arr[i] + arr[j] + arr[k]));
}
k += 1;
}
j += 1;
}
i += 1;
}
if (status == false)
{
print(" \n None\n");
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Triplets = Triplets();
// Define array elements
val arr1: Array < Int > = arrayOf(8, 2, 0, 6, -2, 6, -1, 9, 4, 3);
// Define array elements
val arr2: Array < Int > = arrayOf(9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4);
// Test A
var size: Int = arr1.count();
task.tripletsWithLessThanX(arr1, size, 3);
task.tripletsWithLessThanX(arr1, size, -6);
// Test B
size = arr2.count();
task.tripletsWithLessThanX(arr2, size, -2);
}
Output
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : 3
(2 + 0 + -2) = 0
(2 + 0 + -1) = 1
(2 + -2 + -1) = -1
(0 + -2 + -1) = -3
(0 + -2 + 4) = 2
(0 + -2 + 3) = 1
(0 + -1 + 3) = 2
(-2 + -1 + 4) = 1
(-2 + -1 + 3) = 0
Array : 8 2 0 6 -2 6 -1 9 4 3
Given x : -6
None
Array : 9 2 -7 4 1 3 0 7 22 8 -4
Given x : -2
(2 + -7 + 1) = -4
(2 + -7 + 0) = -5
(2 + -7 + -4) = -9
(-7 + 4 + 0) = -3
(-7 + 4 + -4) = -7
(-7 + 1 + 3) = -3
(-7 + 1 + 0) = -6
(-7 + 1 + -4) = -10
(-7 + 3 + 0) = -4
(-7 + 3 + -4) = -8
(-7 + 0 + -4) = -11
(-7 + 7 + -4) = -4
(-7 + 8 + -4) = -3
(1 + 0 + -4) = -3
Time Complexity Analysis
The tripletsWithLessThanX
function iterates through the array with three nested loops, so its time
complexity is O(n^3), where n is the number of elements in the array.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment