Data Structures and Algorithm Analysis C++ Exercise 7.53(a) and (b) with “sum” o
ID: 3585819 • Letter: D
Question
Data Structures and Algorithm Analysis C++
Exercise 7.53(a) and (b) with “sum” on line 2 of the problem statement replaced with “difference”.
We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8, 4, 1,6, and K is 10, then the answer is yes (4 and 6). A number may be used twice Do the following a. Give an O(N2) algorithm to solve this problem. b. Give an O(N log N) algorithm to solve this problem. (Hint: Sort the items first. 7.53 After that is done, you can solve the problem in linear time.)Explanation / Answer
a)
O(N2) approach is to find every pair's sum and check whether it is equal to 'K'
ALgorithm:
Start:
1. Read the array size, array numbers and 'K'
2. initialize i=0
3. for i = 0 to n-1
j=0
for j = i+1 to n-1
if a[i]+a[j] == k
print "yes"
break
end of inner for loop
end of outer for loop
4. if i==n
print "no"
end
Time complexity = Outer for loop (N) * Inner for loop (N) = O (N2)
b)
Algorithm:
Start:
1. Read the array size, array numbers and 'K'
2. Sort the array in ascending order.
3. Initialize two variables , one variable 'left' to leftmost index '0' and 'right' to rightmost index 'arraysize-1'
4. Loop while left < right:
if ( array[left] + array [right]==K)
print "yes"
break
else if ( array[left] + array [right] >=K)
right = right -1
else
left = left +1
endwhile
5. if (left >= right )
print "no"
end
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.