Challenge: Pair With Target Sum

Lab Python Beginner 10 points

Read a sorted list of numbers and a target. Using two pointers, print the first pair found (smallest left number) that adds up to the target, or No pair.

Input

Line 1: sorted whole numbers separated by spaces. Line 2: the target.

Output

a b with a ≤ b, or No pair.

Example

Input

1 3 4 6 8 11
10

Output

4 6

Sample input available Sample output available

Editor

Python

Hints

Start left = 0, right = last index.

Sum too small? left += 1. Too big? right -= 1.

Solution explanation

Each step moves one pointer, so at most n steps: O(n) instead of O(n²) for checking every pair.

Show solution

nums = list(map(int, input().split()))
target = int(input())
left, right = 0, len(nums) - 1
found = None
while left < right:
    s = nums[left] + nums[right]
    if s == target:
        found = (nums[left], nums[right])
        break
    if s < target:
        left += 1
    else:
        right -= 1
print(f"{found[0]} {found[1]}" if found else "No pair")

Output

Answer