Find and return the number of triplets sum in array/list

Question

1.00/5 (1 vote)

See more:

You have been given a random integer array/list(ARR) and a number X. Find and return the triplet(s) in the array/list which sum to X.
Note :
Given array/list can contain duplicate elements.
Input format :
The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

First line of each test case or query contains an integer 'N' representing the size of the first array/list.

Second line contains 'N' single space separated integers representing the elements in the array/list.

Third line contains an integer 'X'.
Output format :
For each test case, print the total number of triplets present in the array/list.

Output for every test case will be printed in a separate line.
Constraints :
1 <= t <= 10^2
0 <= N <= 10^3
0 <= X <= 10^9
Sample Input 1:

7 Size
1 2 3 4 5 6 7
12
Sample Output 1:
5
Sample Input 2:

7 Size
1 2 3 4 5 6 7
19

Sample Output 2:
0

Explanation for Input 2:
Since there doesn't exist any triplet with sum equal to 19 for the first query, we print 0.

What I have tried:

Java

<pre>public static int tripletSum(int[] arr, int num) {
         int count = 0;
        
        for(int i = 0; i<arr.length; i++){
            
             for(int j = i+1; j<arr.length; j++){
                
                 for (int k = j+1; k<arr.length; k++){
                    
                    if ((arr[i] + arr[j] + arr[k])==num){
                        count++;
                    }
                }
            }
        }
        
         return count;
    }
 }

I get O(n^3) time complexity using this code and Time limit Exceeded error with this. Any way to reduce it to O(n^2) ?

Posted 29-Jul-22 8:25am

Zeeshan Ahmad Jul2022

Updated 26-Feb-23 18:31pm

v2

Add a Solution

Comments

Patrice T 29-Jul-22 14:51pm

Give reference to this challenge.
What site, exact requirement.

Zeeshan Ahmad Jul2022 29-Jul-22 15:20pm

It is actually in my assignment. I can get you the info
You have been given a random integer array/list(ARR) and a number X. Find and return the triplet(s) in the array/list which sum to X.
Note :
Given array/list can contain duplicate elements.
Input format :
The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

First line of each test case or query contains an integer 'N' representing the size of the first array/list.

Second line contains 'N' single space separated integers representing the elements in the array/list.

Third line contains an integer 'X'.
Output format :
For each test case, print the total number of triplets present in the array/list.

Output for every test case will be printed in a separate line.
Constraints :
1 <= t <= 10^2
0 <= N <= 10^3
0 <= X <= 10^9
Sample Input 1:

7 Size
1 2 3 4 5 6 7
12
Sample Output 1:
5
Sample Input 2:

7 Size
1 2 3 4 5 6 7
19

Sample Output 2:
0

Explanation for Input 2:
Since there doesn't exist any triplet with sum equal to 19 for the first query, we print 0.

Patrice T 29-Jul-22 15:23pm

Use Improve question to update your question.
So that everyone can pay attention to this information.

Zeeshan Ahmad Jul2022 29-Jul-22 15:25pm

Done

Afzaal Ahmad Zeeshan 29-Jul-22 18:58pm

There is a reason why this is challenging; you need to think about it. We can solve this, but that would not benefit you.

I recommend reading the Data Structures and Algorithms book to find out how to optimize the algorithms.

Tip: consider using a sliding window.

Zeeshan Ahmad Jul2022 30-Jul-22 1:54am

Okay thank you. I will definitely try it.

2 solutions

Solution 3

Two approaches better than N^3 exist:
Taking advantage of Sort Function:-(NlogN)
1. Using Binary Search for Third number after selecting 2 numbers; would ensure complexity of N^2LogN
2. Carefully Operating over Numbers that is, Select 1 number and then select other 2 from the middle of Remaining Sum and from there if moving the second pointer to right Sum would Increase and moving the first Pointer to left, sum would Decrease total traversal of N for second and Third indices and N for the first. giving an N^2 complexity.

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;

void sort_siei(ll *a,int si,int ei){//ei represents end index+1
    if(ei-si<=1){
        return;
    }
    int mi=si+(ei-si)/2;
    sort_siei(a,si,mi);
    sort_siei(a,mi,ei);
    ll *arr=new ll[ei-si];
    int i=si;
    int j=mi;
    int curr_ind=0;
    while(i<mi&&j<ei){
        if(a[i]<a[j]){
            arr[(curr_ind++)]=a[(i++)];
        }else{
            arr[(curr_ind++)]=a[(j++)];
        }
    }
    while(i<mi){
        arr[(curr_ind++)]=a[(i++)];
    }
    while(j<ei){
        arr[(curr_ind++)]=a[(j++)];
    }
    for(int i=0;i<curr_ind;i++){
        arr[i]=a[si+i];
    }
    delete[] arr;
}  
void merge_sort(ll *a,int n){
    sort_siei(a,0,n);
} 
int main(){
int t;
cin>>t;
while(t--){
    int n;
    cin>>n;
    ll arr[n];
    for(int i=0;i<n;i++){//n
        cin>>arr[i];
    }
    ll x;
    cin>>x;
    int count=0;
    sort(arr,arr+n);
   // merge_sort(arr,n);//nlogn
    for(int i=0;i<(n-2);i++){//O(nsq*logn)
        for(int j=i+1;(2*arr[j]+arr[i])<=x;j++){
            ll curr_sum=arr[i]+arr[j];
            if(binary_search(arr+j+1,arr+n,x-curr_sum)){//LogN
                count++;
            }
        }
    }
    int count2=0;
    //total(n(logn+n))=nsq
    for(int i=0;i<n-2;i++){//n
        ll rem_sum=x-arr[i];
        int k=upper_bound(arr,arr+n,rem_sum/2)-arr;//logn
        int j=k-1;
        while(j>i&&k<n){//n
            if((arr[j]+arr[k])>rem_sum){
                j--;
            }
            else if((arr[j]+arr[k])<rem_sum){
                k++;
            }
            else{//equality
                //count2++;
                if(j==(i+1)){
                    ll cuur_value=arr[k];
                    while(arr[k]==cuur_value){
                        k++;
                        count2++;
                    }
                }
                else if((k==n-1)||(arr[j-1]==arr[j])){
                    ll cuur_value=arr[j];
                    while(arr[j]==cuur_value){
                        j--;
                        count2++;
                    }
                    k++;
                }
                else if(arr[k+1]==arr[k]){
                       ll cuur_value=arr[k];
                    while(arr[k]==cuur_value){
                        k++;
                        count2++;
                    }
                    j--;
                }
                else{
                    k++;
                    j--;
                    count2++;
                }
            }
        }
    }
    cout<<"count1"<<count<<"\nCount2"<<count2;
}
}

Posted 26-Feb-23 18:31pm

Member 15935824

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Accepted Answer · 2022-07-29T11:51:00

Quote:
I get O(n^3) time complexity using this code and Time limit Exceeded error with this. Any way to reduce it to O(n^2) ?

My advice: sort the array in reverse, then take advantage of sorted array.

1 5 4 7 2 6 3
sorted in reverse gives
7 6 5 4 3 2 1

Then because the array is sorted, you can do early cut in search.
Hints:

For a triplet
if (arr[i]+arr[i+1]+arr[i+2] < num){
    // end of search
}
//Same apply to couple

When you found a triplet
if (arr[x]+arr[y]+arr[z] == num){
next triplet (if there is one) with same x will have nexty >= y and nextz <= z
if (arr[x]+arr[nexty]+arr[nextz] == num){

Find and return the number of triplets sum in array/list

2 solutions

Solution 1

Solution 3

Add your solution here

Preview 0

Find and return the number of triplets sum in array/list

2 solutions

Solution 1

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us