Challenge: Pair With Target Sum

Lab C++ Beginner 10 points

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

Input

Line 1: n. Line 2: n sorted whole numbers. Line 3: the target.

Output

a b with a ≤ b, or No pair.

Example

Input

6
1 3 4 6 8 11
10

Output

4 6

Sample input available Sample output available

Editor

C++

Hints

Start l = 0, r = n - 1.

Sum too small: l++. Too big: r--.

Solution explanation

Each step moves one pointer: O(n) instead of O(n²).

Show solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    int target;
    cin >> target;
    int l = 0, r = n - 1;
    while (l < r) {
        int s = v[l] + v[r];
        if (s == target) {
            cout << v[l] << " " << v[r] << endl;
            return 0;
        }
        if (s < target) l++;
        else r--;
    }
    cout << "No pair" << endl;
    return 0;
}

Output

Answer