I have written code which works in o(nlogn) time and want to solve it in n time…
#include
#include
using namespace std;
void GetInput(int arr[],int n)
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
}
//function of binary search
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
//function to print pairs
void printPairs(int arr[],int n,int total)
{
sort(arr,arr+n);
for(int i=0;i<n;i++)
{
int currdigit = arr[i];
int neededdigit = total - currdigit;
if(neededdigit<0)
{
neededdigit = neededdigit * -1;
}
int number = binarySearch(arr,0,n,neededdigit);
if(number > i)
{
cout<<currdigit<<" and "<<neededdigit<<endl;
}
}
}
int main() {
int n;
cin>>n;
int arr[n];
GetInput(arr,n);
int total;
cin>>total;
printPairs(arr,n,total);
return 0;
}