Pair Sum in Sorted Array

Lab C Intermediate 20 points

Read a sorted array and a target. Using two indexes from both ends, print the first pair a b that sums to the target (smallest a), or none.

Input

n, the sorted integers, then the target.

Output

One line.

Example

Input

6
1 2 4 7 11 15
15

Output

4 11

Sample input available Sample output available

Editor

Hints

If the sum is too small, move the left index right; if too big, move the right index left.

Solution explanation

Sorted input lets two pointers find the pair in O(n).

Show solution

#include <stdio.h>

int main() {
    int n, a[100], target;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &target);
    int i = 0, j = n - 1, found = 0;
    while (i < j) {
        int s = a[i] + a[j];
        if (s == target) {
            printf("%d %d\n", a[i], a[j]);
            found = 1;
            break;
        }
        if (s < target) i++;
        else j--;
    }
    if (!found) printf("none\n");
    return 0;
}

Output

Answer