Int Sum 0 Int Item 0 Do Item Sum Item if Sum 4 Continue While Item 5
Given an array of distinct elements. The task is to find triplets in the array whose sum is zero.
Examples :
Input: arr[] = {0, -1, 2, -3, 1}
Output: (0 -1 1), (2 -3 1)
Explanation: The triplets with zero sum are 0 + -1 + 1 = 0 and 2 + -3 + 1 = 0Input: arr[] = {1, -2, 1, 0, 5}
Output: 1 -2 1
Explanation: The triplets with zero sum is 1 + -2 + 1 = 0
Naive approach: Below is the idea to solve the problem
Run three loops and check one by one whether the sum of the three elements is zero or not. If the sum of three elements is zero then print elements otherwise print not found.
Follow the below steps to Implement the Idea:
- Run three nested loops with loop counter i, j, k
- The first loops will run from 0 to n-3 and second loop from i+1 to n-2 and the third loop from j+1 to b. The loop counter represents the three elements of the triplet.
- Check if the sum of elements at i'th, j'th, k'th is equal to zero or not. If yes print the sum else continue.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void findTriplets( int arr[], int n)
{
bool found = false ;
for ( int i = 0; i < n - 2; i++) {
for ( int j = i + 1; j < n - 1; j++) {
for ( int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == 0) {
cout << arr[i] << " " << arr[j] << " "
<< arr[k] << endl;
found = true ;
}
}
}
}
if (found == false )
cout << " not exist " << endl;
}
int main()
{
int arr[] = { 0, -1, 2, -3, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
findTriplets(arr, n);
return 0;
}
C
#include <stdbool.h>
#include <stdio.h>
void findTriplets( int arr[], int n)
{
bool found = false ;
for ( int i = 0; i < n - 2; i++) {
for ( int j = i + 1; j < n - 1; j++) {
for ( int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == 0) {
printf ( "%d %d %d\n" , arr[i], arr[j],
arr[k]);
found = true ;
}
}
}
}
if (found == false )
printf ( " not exist \n" );
}
int main()
{
int arr[] = { 0, -1, 2, -3, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
findTriplets(arr, n);
return 0;
}
Java
import java.io.*;
import java.util.*;
class num {
static void findTriplets( int [] arr, int n)
{
boolean found = false ;
for ( int i = 0 ; i < n - 2 ; i++) {
for ( int j = i + 1 ; j < n - 1 ; j++) {
for ( int k = j + 1 ; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == 0 ) {
System.out.println(arr[i] + " "
+ arr[j] + " "
+ arr[k]);
found = true ;
}
}
}
}
if (found == false )
System.out.println( " not exist " );
}
public static void main(String[] args)
{
int arr[] = { 0 , - 1 , 2 , - 3 , 1 };
int n = arr.length;
findTriplets(arr, n);
}
}
Python3
def findTriplets(arr, n):
found = False
for i in range ( 0 , n - 2 ):
for j in range (i + 1 , n - 1 ):
for k in range (j + 1 , n):
if (arr[i] + arr[j] + arr[k] = = 0 ):
print (arr[i], arr[j], arr[k])
found = True
if (found = = False ):
print ( " not exist " )
arr = [ 0 , - 1 , 2 , - 3 , 1 ]
n = len (arr)
findTriplets(arr, n)
C#
using System;
class GFG {
static void findTriplets( int [] arr, int n)
{
bool found = false ;
for ( int i = 0; i < n - 2; i++) {
for ( int j = i + 1; j < n - 1; j++) {
for ( int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == 0) {
Console.Write(arr[i]);
Console.Write( " " );
Console.Write(arr[j]);
Console.Write( " " );
Console.Write(arr[k]);
Console.Write( "\n" );
found = true ;
}
}
}
}
if (found == false )
Console.Write( " not exist " );
}
public static void Main()
{
int [] arr = { 0, -1, 2, -3, 1 };
int n = arr.Length;
findTriplets(arr, n);
}
}
PHP
<?php
function findTriplets( $arr , $n )
{
$found = false;
for ( $i = 0; $i < $n - 2; $i ++)
{
for ( $j = $i + 1; $j < $n - 1; $j ++)
{
for ( $k = $j + 1; $k < $n ; $k ++)
{
if ( $arr [ $i ] + $arr [ $j ] +
$arr [ $k ] == 0)
{
echo $arr [ $i ] , " " ,
$arr [ $j ] , " " ,
$arr [ $k ] , "\n" ;
$found = true;
}
}
}
}
if ( $found == false)
echo " not exist " , "\n" ;
}
$arr = array (0, -1, 2, -3, 1);
$n = sizeof( $arr );
findTriplets( $arr , $n );
?>
Javascript
<script>
arr = [0, -1, 2, -3, 1];
function findTriplets(arr) {
let found = false ;
for (let i = 0; i < arr.length - 2; i++) {
for (let j = i + 1; j < arr.length - 1; j++) {
for (let k = j + 1; k < arr.length; k++) {
if (arr[i] + arr[j] + arr[k] === 0)
{
document.write(arr[i]);
document.write( " " );
document.write(arr[j]);
document.write( " " );
document.write(arr[k]);
document.write( "<br>" );
found = true ;
}
}
}
if (found === false ) {
document.write( " not exist " );
}
}
}
findTriplets(arr);
</script>
Time Complexity: O(n3), As three nested loops are required, so the time complexity is O(n3).
Auxiliary Space: O(1), Since no extra space is required, so the space complexity is constant.
Find all triplets with zero sum using Hashing
Below is the idea to solve the problem
This involves traversing through the array. For every element arr[i], find a pair with sum "-arr[i]". This problem reduces to pair sum and can be solved in O(n) time using hashing.
Follow the steps below to implement the idea:
- Create a Hashmap to store a key-value pair.
- Run a nested loop with two loops, the outer loop from 0 to n-2 and the inner loop from i+1 to n-1
- Check if the sum of ith and jth element multiplied with -1 is present in the Hashmap or not
- If the element is present in the Hashmap, print the triplet else insert the j'th element in the Hashmap.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void findTriplets( int arr[], int n)
{
bool found = false ;
for ( int i = 0; i < n - 1; i++) {
unordered_set< int > s;
for ( int j = i + 1; j < n; j++) {
int x = -(arr[i] + arr[j]);
if (s.find(x) != s.end()) {
printf ( "%d %d %d\n" , x, arr[i], arr[j]);
found = true ;
}
else
s.insert(arr[j]);
}
}
if (found == false )
cout << " No Triplet Found" << endl;
}
int main()
{
int arr[] = { 0, -1, 2, -3, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
findTriplets(arr, n);
return 0;
}
Java
import java.io.*;
import java.util.*;
class GFG {
static void findTriplets( int arr[], int n)
{
boolean found = false ;
for ( int i = 0 ; i < n - 1 ; i++) {
HashSet<Integer> s = new HashSet<Integer>();
for ( int j = i + 1 ; j < n; j++) {
int x = -(arr[i] + arr[j]);
if (s.contains(x)) {
System.out.printf( "%d %d %d\n" , x,
arr[i], arr[j]);
found = true ;
}
else {
s.add(arr[j]);
}
}
}
if (found == false ) {
System.out.printf( " No Triplet Found\n" );
}
}
public static void main(String[] args)
{
int arr[] = { 0 , - 1 , 2 , - 3 , 1 };
int n = arr.length;
findTriplets(arr, n);
}
}
Python3
def findTriplets(arr, n):
found = False
for i in range (n - 1 ):
s = set ()
for j in range (i + 1 , n):
x = - (arr[i] + arr[j])
if x in s:
print (x, arr[i], arr[j])
found = True
else :
s.add(arr[j])
if found = = False :
print ( "No Triplet Found" )
arr = [ 0 , - 1 , 2 , - 3 , 1 ]
n = len (arr)
findTriplets(arr, n)
C#
using System;
using System.Collections.Generic;
class GFG {
static void findTriplets( int [] arr, int n)
{
bool found = false ;
for ( int i = 0; i < n - 1; i++) {
HashSet< int > s = new HashSet< int >();
for ( int j = i + 1; j < n; j++) {
int x = -(arr[i] + arr[j]);
if (s.Contains(x)) {
Console.Write( "{0} {1} {2}\n" , x,
arr[i], arr[j]);
found = true ;
}
else {
s.Add(arr[j]);
}
}
}
if (found == false ) {
Console.Write( " No Triplet Found\n" );
}
}
public static void Main(String[] args)
{
int [] arr = { 0, -1, 2, -3, 1 };
int n = arr.Length;
findTriplets(arr, n);
}
}
Javascript
<script>
function findTriplets(arr, n)
{
var found = false ;
for ( var i = 0; i < n - 1; i++)
{
var s = new Set();
for ( var j = i + 1; j < n; j++)
{
var x = -(arr[i] + arr[j]);
if (s.has(x))
{
document.write( x + " " + arr[i] + " " + arr[j] + "<br>" );
found = true ;
}
else
s.add(arr[j]);
}
}
if (found == false )
document.write( " No Triplet Found" );
}
var arr = [0, -1, 2, -3, 1];
var n = arr.length;
findTriplets(arr, n);
</script>
Time Complexity: O(n2), Since two nested loops are required, so the time complexity is O(n2).
Auxiliary Space: O(n), Since a Hashmapis required, so the space complexity is linear.
Find all triplets with zero sum using Sorting :
The idea is based on the above discussed approach using Hashmap of this post. For every element check that there is a pair whose sum is equal to the negative value of that element.
Follow the steps below to implement the idea:
- Sort the array in ascending order.
- Traverse the array from start to end.
- For every index i, create two variables l = i + 1 and r = n – 1
- Run a loop until l is less than r if the sum of array[i], array[l] and array[r] is equal to zero then print the triplet and break the loop
- If the sum is less than zero then increment the value of l, by increasing the value of l the sum will increase as the array is sorted, so array[l+1] > array [l]
- If the sum is greater than zero then decrement the value of r, by decreasing the value of r the sum will decrease as the array is sorted, so array[r-1] < array [r].
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void findTriplets( int arr[], int n)
{
bool found = false ;
sort(arr, arr + n);
for ( int i = 0; i < n - 1; i++) {
int l = i + 1;
int r = n - 1;
int x = arr[i];
while (l < r) {
if (x + arr[l] + arr[r] == 0) {
printf ( "%d %d %d\n" , x, arr[l], arr[r]);
l++;
r--;
found = true ;
}
else if (x + arr[l] + arr[r] < 0)
l++;
else
r--;
}
}
if (found == false )
cout << " No Triplet Found" << endl;
}
int main()
{
int arr[] = { 0, -1, 2, -3, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
findTriplets(arr, n);
return 0;
}
Java
import java.io.*;
import java.util.Arrays;
class GFG {
static void findTriplets( int arr[], int n)
{
boolean found = false ;
Arrays.sort(arr);
for ( int i = 0 ; i < n - 1 ; i++) {
int l = i + 1 ;
int r = n - 1 ;
int x = arr[i];
while (l < r) {
if (x + arr[l] + arr[r] == 0 ) {
System.out.print(x + " " );
System.out.print(arr[l] + " " );
System.out.println(arr[r] + " " );
l++;
r--;
found = true ;
}
else if (x + arr[l] + arr[r] < 0 )
l++;
else
r--;
}
}
if (found == false )
System.out.println( " No Triplet Found" );
}
public static void main(String[] args)
{
int arr[] = { 0 , - 1 , 2 , - 3 , 1 };
int n = arr.length;
findTriplets(arr, n);
}
}
Python3
def findTriplets(arr, n):
found = False
arr.sort()
for i in range ( 0 , n - 1 ):
l = i + 1
r = n - 1
x = arr[i]
while (l < r):
if (x + arr[l] + arr[r] = = 0 ):
print (x, arr[l], arr[r])
l + = 1
r - = 1
found = True
elif (x + arr[l] + arr[r] < 0 ):
l + = 1
else :
r - = 1
if (found = = False ):
print ( " No Triplet Found" )
arr = [ 0 , - 1 , 2 , - 3 , 1 ]
n = len (arr)
findTriplets(arr, n)
C#
using System;
public class GFG {
static void findTriplets( int [] arr, int n)
{
bool found = false ;
Array.Sort(arr);
for ( int i = 0; i < n - 1; i++) {
int l = i + 1;
int r = n - 1;
int x = arr[i];
while (l < r) {
if (x + arr[l] + arr[r] == 0) {
Console.Write(x + " " );
Console.Write(arr[l] + " " );
Console.WriteLine(arr[r] + " " );
l++;
r--;
found = true ;
}
else if (x + arr[l] + arr[r] < 0)
l++;
else
r--;
}
}
if (found == false )
Console.WriteLine( " No Triplet Found" );
}
static public void Main()
{
int [] arr = { 0, -1, 2, -3, 1 };
int n = arr.Length;
findTriplets(arr, n);
}
}
PHP
<?php
function findTriplets( $arr , $n )
{
$found = false;
sort( $arr );
for ( $i = 0; $i < $n - 1; $i ++)
{
$l = $i + 1;
$r = $n - 1;
$x = $arr [ $i ];
while ( $l < $r )
{
if ( $x + $arr [ $l ] +
$arr [ $r ] == 0)
{
echo $x , " " , $arr [ $l ],
" " , $arr [ $r ], "\n" ;
$l ++;
$r --;
$found = true;
}
else if ( $x + $arr [ $l ] +
$arr [ $r ] < 0)
$l ++;
else
$r --;
}
}
if ( $found == false)
echo " No Triplet Found" , "\n" ;
}
$arr = array (0, -1, 2, -3, 1);
$n = sizeof( $arr );
findTriplets( $arr , $n );
?>
Javascript
<script>
function findTriplets(arr, n)
{
let found = false ;
arr.sort((a, b) => a - b);
for (let i=0; i<n-1; i++)
{
let l = i + 1;
let r = n - 1;
let x = arr[i];
while (l < r)
{
if (x + arr[l] + arr[r] == 0)
{
document.write(x + " " );
document.write(arr[l]+ " " );
document.write(arr[r]+ " " + "<br>" );
l++;
r--;
found = true ;
}
else if (x + arr[l] + arr[r] < 0)
l++;
else
r--;
}
}
if (found == false )
document.write( " No Triplet Found" + "<br>" );
}
let arr = [0, -1, 2, -3, 1];
let n = arr.length;
findTriplets(arr, n);
</script>
Time Complexity: O(n2), Only two nested loops are required, so the time complexity is O(n2).
Auxiliary Space: O(1), no extra space is required, so the space complexity is constant.
This article is contributed by DANISH_RAZA. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Source: https://www.geeksforgeeks.org/find-triplets-array-whose-sum-equal-zero/
0 Response to "Int Sum 0 Int Item 0 Do Item Sum Item if Sum 4 Continue While Item 5"
Post a Comment