Arrays-Target Sum Pairs Doubt

#1

#include
using namespace std;
int main()
{
int n,max=-1,c;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
if(max<arr[i])
max=arr[i];
}
cin>>c;

int count[max]={0};
for(int i=0;i<n;i++){
count[arr[i]]++;
}

for(int i=0;i<n;i++)
{
int val=arr[i];
int num = c-val;
int temp;
if(count[num]&&count[num]>0)
{
if(num>arr[i])
{
temp=num;
num=val;
val=temp;
}
cout<<num<<" and "<<val<<endl;
count[num]=0;
count[val]=0;
}
}
return 0;
}

//Not Able to pass all the test cases. Kindly provide the hint

#2

@Sanket first sort the array then apply two loop and if arr[i]+arr[j]==sum then print arr[i] and arr[j] this will take o(n^2) time

#3

Any optimized way. It will be very helpful.
Yes the suggested method is giving correct answer.

#4

A more efficient solution would be to sort the array and having two pointers to scan the array from the beginning and the end at the same time. If the sum of the values in left and right pointers equals to k, we output the pair. If the sum is less than k then we advance the left pointer, else if the sum is greater than k we decrement the right pointer, until both pointers meet at some part of the array. The complexity of this solution is O(NlogN) due to sorting. This called as two pointer approach

1 Like