Challenge: Two Sum

Lab C++ Beginner 10 points

Read n numbers and a target. Print the indexes of the two numbers that add up to the target, smaller index first. There is exactly one answer. Aim for O(n) with unordered_map.

Input

Line 1: n target. Line 2: n whole numbers.

Output

i j

Example

Input

4 9
2 7 11 15

Output

0 1

Sample input available Sample output available

Editor

C++

Hints

The partner of x is target - x.

Check the map before adding the current number.

Solution explanation

Keep reading after the answer so every input number is consumed; each lookup is O(1).

Show solution

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

int main() {
    int n, target;
    cin >> n >> target;
    unordered_map<int, int> seen;
    bool done = false;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (!done && seen.count(target - x)) {
            cout << seen[target - x] << " " << i << endl;
            done = true;
        }
        seen[x] = i;
    }
    return 0;
}

Output

Answer