Please help me with Problem 3 Textbook: Introduction To Algorithms 3rd Edition (
ID: 3663233 • Letter: P
Question
Please help me with Problem 3
Textbook: Introduction To Algorithms 3rd Edition
(2.3-7 Describe a ‚.n lg n/-time algorithm that, given a set S of n integers and another
integer x, determines whether or not there exist two elements in S whose sum is
exactly x.)
Problem 3. Modification of Exercise 2.3-7. Assume that < A, n > is a sorted array of integers,
and x is also an integer. Design an algorithm that in Q(n) steps finds i and j such that
A[i] + A[j] = x or establishes that such i and j do not exist.
Hint: start by checking the value A[0] + A[n 1]; obviously it is very nice if this value equals x.
What can you conclude if this value is smaller than x? What can you conclude if this value is
larger than x?
Explanation / Answer
while looping.. if a[0]+a[n-1] equals... then it is good
or if it is smaller .. then it shows that it diesnt matched with any numbers in array since array is sorted
or if resuls is larger .. then we will increment i and decrement j values and continue process until found
//storing length of sorted array
int j = array.size()
//looping through arrays
int x = 10 //let us assume
for(int i=0;i<j;i++){
if((array[i] + array[j-1]) == x){
print(" i and j")
}
else if((array[i] + array[j-1]) < x){
print(no matched i and j );
}
else if((array[i] + array[j-1]) > x){
j--;
}
}