Check if all possible Triplet Sum is present in given Array
Given an array arr[] of size N, the task is to check if for all distinct triplets of indices i, j, k, [ 0 ≤ i < j < k ≤ N-1 ] the sum arr[i]+arr[j]+arr[k] is present in the array.
Examples:
Input: arr[] = {-1, 0, 0, 1}
Output: True
Explanation: For index 0, 1, 2: arr[i]+arr[j]+arr[k] = -1 + 0 + 0 = -1
For index 0, 1, 3: arr[i]+arr[j]+arr[k] = -1 + 0 + 1 = 0
For index 0, 2, 3: arr[i]+arr[j]+arr[k] = -1 + 0 + 1 = 0
For index 1, 2, 3: arr[i]+arr[j]+arr[k] = 0 + 0 + 1 = 1
-1, 0, 1 all are elements of the array arr[], so, the condition holds true.Input: arr[] = {0, 0, 0}
Output: True
Approach: The problem can be solved using the following mathematical idea:
If there are more than or equal to 3 positive elements or more than or equal to 3 negative elements, then the condition arr[i]+arr[j]+arr[k] = an element of the array cannot be true.
Otherwise, push all the element of the array in a linear data structure like vector and if there are more than one zero in the array then push only one 0 in the vector, the vector will contain atmost 5 elements i.e., 2 positives, 2 negatives and 1 zero.
Now, push all elements into a set for checking the condition, and apply bruteforce because there are only 5 elements atmost in the array. For checking the condition of the question, check if v[i]+v[j]+v[k] is present in the set or not for all the triplets from the vector.
Follow the steps mentioned below to implement the observation:
- Initialize variables (say CP = 0, and CN = 0) for counting positives and negatives respectively.
- Run a loop and push all the elements of the array in the vector.
- If CP > 2 or CN < 2 at any point of time then the given condition cannot be satisfied. So return false.
- Push only one 0 if there are at least one 0 into the vector.
- Now apply three nested loops and find if the condition holds true or not.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to find the condition is true or not bool solve( int * arr, int n) { // Initialize the variables int CP = 0, CN = 0; vector< int > v; bool f = 1; // Count the number of positives and negatives // in the original array and put it into vector for ( int i = 0; i < n; i++) { if (arr[i] > 0) { v.push_back(arr[i]); CP++; } else if (arr[i] < 0) { v.push_back(arr[i]); CN++; } else { if (f) v.push_back(arr[i]); f = 0; } if (CP > 2 || CN > 2) break ; } // If there are more than 2 positives or // 2 negatives then return 0 if (CP > 2 || CN > 2) return 0; // Else case else { // Put elements of vector into the set set< int > s; for ( int i = 0; i < v.size(); i++) { s.insert(v[i]); } // Check the condition for every index for ( int i = 0; i < v.size(); i++) { for ( int j = i + 1; j < v.size(); j++) { for ( int k = j + 1; k < v.size(); k++) { // If element is not present // then the pointer // points to s.end() if (s.find(v[i] + v[j] + v[k]) == s.end()) { return 0; } } } } // The condition is true for all indexes // so, return 1 return 1; } } // Driver Code int main() { int arr[] = { -1, 0, 0, 1 }; int N = sizeof (arr) / sizeof (arr[0]); if (solve(arr, N)) cout << "True" << endl; else cout << "False" << endl; return 0; } |
Java
// Java code to implement the above approach import java.util.*; class GFG{ // Function to find the condition is true or not static boolean solve( int [] arr, int n) { // Initialize the variables int CP = 0 , CN = 0 ; Vector<Integer> v = new Vector<>(); boolean f = true ; // Count the number of positives and negatives // in the original array and put it into vector for ( int i = 0 ; i < n; i++) { if (arr[i] > 0 ) { v.add(arr[i]); CP++; } else if (arr[i] < 0 ) { v.add(arr[i]); CN++; } else { if (f) v.add(arr[i]); f = false ; } if (CP > 2 || CN > 2 ) break ; } // If there are more than 2 positives or // 2 negatives then return 0 if (CP > 2 || CN > 2 ) return false ; // Else case else { // Put elements of vector into the set HashSet<Integer> s = new HashSet<>(); for ( int i = 0 ; i < v.size(); i++) { s.add(v.get(i)); } // Check the condition for every index for ( int i = 0 ; i < v.size(); i++) { for ( int j = i + 1 ; j < v.size(); j++) { for ( int k = j + 1 ; k < v.size(); k++) { // If element is not present // then the pointer // points to s.end() if (!s.contains(v.get(i) + v.get(j) + v.get(k))) { return false ; } } } } // The condition is true for all indexes // so, return 1 return true ; } } // Driver Code public static void main(String[] args) { int arr[] = { - 1 , 0 , 0 , 1 }; int N = arr.length; if (solve(arr, N)) System.out.print( "True" + "\n" ); else System.out.print( "False" + "\n" ); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 code to implement the above approach def solve(arr, n): # Initialize the variables CP = 0 CN = 0 v = [] f = True # Count the number of positives and negatives # in the original array and put it into array for i in range (n): if (arr[i] > 0 ): v.append(arr[i]) CP + = 1 elif (arr[i] < 0 ): v.append(arr[i]) CN + = 1 else : if (f): v.append(arr[i]) f = False if (CP > 2 or CN > 2 ): break # If there are more than 2 positives or 2 negatives then return 0 if (CP > 2 or CN > 2 ): return False # Else case else : # Put element of array into the set s = set () for i in range ( len (v)): s.add(v[i]) # Check the condition for every index for i in range ( len (v)): for j in range (i + 1 , len (v), 1 ): for k in range (j + 1 , len (v), 1 ): # If element is not present then the pointer points to s if ((v[i] + v[j] + v[k]) not in s): return False return True arr = [ - 1 , 0 , 0 , 1 ] N = len (arr) if (solve(arr, N)): print ( "True" ) else : print ( "False" ) # This code is contributed by lokeshmvs21. |
C#
// C# code to implement the above approach using System; using System.Collections.Generic; public class GFG{ // Function to find the condition is true or not static bool solve( int [] arr, int n) { // Initialize the variables int CP = 0, CN = 0; List< int > v = new List< int >(); bool f = true ; // Count the number of positives and negatives // in the original array and put it into vector for ( int i = 0; i < n; i++) { if (arr[i] > 0) { v.Add(arr[i]); CP++; } else if (arr[i] < 0) { v.Add(arr[i]); CN++; } else { if (f) v.Add(arr[i]); f = false ; } if (CP > 2 || CN > 2) break ; } // If there are more than 2 positives or // 2 negatives then return 0 if (CP > 2 || CN > 2) return false ; // Else case else { // Put elements of vector into the set HashSet< int > s = new HashSet< int >(); for ( int i = 0; i < v.Count; i++) { s.Add(v[i]); } // Check the condition for every index for ( int i = 0; i < v.Count; i++) { for ( int j = i + 1; j < v.Count; j++) { for ( int k = j + 1; k < v.Count; k++) { // If element is not present // then the pointer // points to s.end() if (!s.Contains(v[i] + v[j] + v[k])) { return false ; } } } } // The condition is true for all indexes // so, return 1 return true ; } } // Driver Code public static void Main(String[] args) { int []arr = { -1, 0, 0, 1 }; int N = arr.Length; if (solve(arr, N)) Console.Write( "True" + "\n" ); else Console.Write( "False" + "\n" ); } } // This code contributed by shikhasingrajput |
Javascript
<script> // JavaScript code to implement the above approach // Function to find the condition is true or not const solve = (arr, n) => { // Initialize the variables let CP = 0, CN = 0; let v = []; let f = 1; // Count the number of positives and negatives // in the original array and put it into vector for (let i = 0; i < n; i++) { if (arr[i] > 0) { v.push(arr[i]); CP++; } else if (arr[i] < 0) { v.push(arr[i]); CN++; } else { if (f) v.push(arr[i]); f = 0; } if (CP > 2 || CN > 2) break ; } // If there are more than 2 positives or // 2 negatives then return 0 if (CP > 2 || CN > 2) return 0; // Else case else { // Put elements of vector into the set let s = new Set(); for (let i = 0; i < v.length; i++) { s.add(v[i]); } // Check the condition for every index for (let i = 0; i < v.length; i++) { for (let j = i + 1; j < v.length; j++) { for (let k = j + 1; k < v.length; k++) { // If element is not present // then the pointer // points to s.end() if (!s.has(v[i] + v[j] + v[k])) { return 0; } } } } // The condition is true for all indexes // so, return 1 return 1; } } // Driver Code let arr = [-1, 0, 0, 1]; let N = arr.length; if (solve(arr, N)) document.write( "True<br/>" ); else document.write( "False<br/>" ); // This code is contributed by rakeshsahni </script> |
True
Time Complexity: O(N)
- The frequency count takes O(N) time
- The final vector can have at most 5 elements, So 3 nested loops will take at most O(1) time
Auxiliary Space: O(1)