Given a list of n integers sorted in nondecreasing order and target integer t, c

Question

Given a list of n integers sorted in nondecreasing order and target integer t, checks whether or not the list contains two integers x and y whose sum is equal to t. If the answer is YES, we want to find any such pair (x, y) of integers (not all). In PSS2, we solved this problem in quadratic time. In this problem, we will take advantage of the fact thet the array is sorted to solve it more efficiently. We will use two different approaches. a) The idea is to use the binary search function n times ... (x - t rof hcraes, yarra eht fo x themele hcae roF) Call your function bool fastSorted2SumA(const int A[], int n, int t, int & x, int & y); Thus x and y if found are returned by reference. b) The idea is to use two counters: i initialized to 0 and j to n - 1 .... try to do something similar to the merge function. Compare A[] + A[] to t, and accordingly decide how to move i and. The objective is to achieve linear time. Hence (b) should be faster then (a). Call your function bool fastSorted2SumB(const int A[], int n, int t, int & x, int & y); Write a program to test your functions.

Explanation / Answer

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <climits>
using namespace std;

// Time Complexity: O(nlogn)
bool fastSorted2SumA (const int A[], int n, int t, int &x, int &y)
{
int c =0;
for(int i=0;i<n;i++)
{
//binary search of t//
int search_num=t-A[i];
int lb=0,ub=n-1,flag=0,mid;
if(search_num>0)
{
while(lb<=ub)
{
mid=(lb+ub)/2;
if(A[mid]==search_num)
{
flag=1;
break;
}
else if(A[mid]>search_num)
ub=mid-1;
else
lb=mid+1;
}
}
if(flag==1&&mid!=i){
printf("Using fastSorted2SumA X: %d, Y: %d ",A[i],A[mid]);
x = A[i];
y = A[mid];
n=n-1; //decreasig the size of the Aay to stop reapeating ans like (1,11) (11,1)//
c++;
}
}
if(c == 0)
return false;
else return true;
}

// Time Complexity: O(n)
bool fastSorted2SumB (const int A[], int n, int t, int &x, int &y)
{
int i, temp;
bool binMap[10000] = {0};
int c = 0;
for (i = 0; i < n; i++)
{
temp = t - A[i];
if (temp >= 0 && binMap[temp] == 1)
{
printf("Using fastSorted2SumB X: %d, Y: %d ", A[i], temp);
x = A[i];
y = temp;
c++;
}
binMap[A[i]] = 1;
}
if(c == 0) return false;
else return true;
}

int main()
{
int n;
cout << "Enter size of list: ";
cin >> n;

int A[n];
cout << "Enter elements of list: ";
for (int i = 0; i < n; ++i)
{
cin >> A[i];
}
sort(A,A+n); // sorting array first
int t;
cout << "Enter target value: ";
cin >> t;

int x, y;
bool value1 = fastSorted2SumA(A,n,t,x,y);
bool value2 = fastSorted2SumB(A,n,t,x,y);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.