Target sum pairs

#1

#include
#include
using namespace std;
void sum(int a[],int n,int target)
{
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(target==(a[i]+a[j]))
{
cout<<a[i]<<" and "<<a[j]<<endl;

		  }

	   }

  
}

}
int main() {
int a[2000];
int n;
int target;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cin>>target;
sort(a,a+n);
sum(a,n,target);
return 0;
}
my code is this and it passing all test cases but complexity is order of n square is there any efficient way to do it

Target sum pairs
#2

Yes there is a more efficient way to solve this question, after sorting the array when you are iterating the array, if your current element is a[i], If there exists some other element which a[x] such that a[i] + a[x] = target, then a[x] = target - a[i], since the array is sorted we can just binary search if a[x] is present in the array if it is then print the pair else dont. This will bring the complexity down to O(nlogn)

#3

Can we do it in order of n time complexity?

#4

Yes it is possible to do with the help of hashing, here is the algorithm to do it:

  1. Create a map to store frequency of each number in the array.
  2. now while iterating the array check if the target - a[i] is present in the map if yes than target can be formed with the help of current element.
1 Like
#5

Ohk thanks sir… For clearing it…