Question

Submit an implementation for this algorithm in C+ +, PHP or Python. Indicate the runtime of your solution. Assume that you are given two lists, A[L.x] and B[Ly), each sorted in nondescending order. Design an algorithm to determine if there are two values q e A and r E B such that q + r = 100. For full points, your solution must run in linear time. Partial credit may be given to correct but less efficient solutions.

Answer 1

Answer: def find_sum_pairs(A, B):

i = 0 # Pointer for list A

j = len(B) - 1 # Pointer for list B

while i < len(A) and j >= 0:

current_sum = A[i] + B[j]

if current_sum == 100:

return True # Found a pair with sum 100

if current_sum < 100:

i += 1 # Move pointer in list A to the right

else:

j -= 1 # Move pointer in list B to the left

return False # No pair with sum 100 found

# Test the function

A = [10, 20, 30, 40, 50]

B = [40, 50, 60, 70, 80]

print(find_sum_pairs(A, B)) # Output: True

A = [10, 20, 30, 40, 50]

B = [60, 70, 80, 90, 100]

print(find_sum_pairs(A, B)) # Output: False

Step-by-step explanation:

The algorithm uses two pointers, i for list A and j for list B, initialized to the start and end of their respective lists.

It enters a loop that continues until either i exceeds the length of A or j becomes negative.

At each iteration, it calculates the sum of the elements pointed by i and j and checks if it's equal to 100.

If the sum is equal to 100, it returns True as we found a pair with the desired sum.

If the sum is less than 100, it increments i to consider a larger element from list A.

If the sum is greater than 100, it decrements j to consider a smaller element from list B.

If the loop completes without finding a pair with sum 100, it returns False.

The runtime of this solution is linear, O(L + Ly), as both pointers traverse their respective lists only once in a single pass.