sum-of-two-values

Sum of Two Values

CSES easy

You are given an array of \(n\) integers, and your task is to find two distinct positions \(i \ne j\) such that:

\(a_i + a_j = x.\)

If there are multiple valid pairs, you may output any of them. If no such pair exists, output IMPOSSIBLE.

Constraints:

\(1 \le n \le 2 \cdot 10^5\)
\(1 \le x, a_i \le 10^9\)

Input:

First line: two integers \(n\) and \(x\) — the array size and the target sum.
Second line: \(n\) integers \(a_1, a_2, \dots, a_n\) — the array values.

Output:

Either two 1-based positions i j with \(a_i + a_j = x\) and \(i \ne j\),
Or IMPOSSIBLE if no such pair exists.

Example:

Input:

4 8
2 7 5 1

Output:

2 4

(one valid pair is \(7 + 1 = 8\))

Solution

We want to find two numbers that sum to \(x\) in \(O(n log(n))\) time.

A straightforward approach is to use a map that remembers what we’ve seen so far:

Iterate through the array from left to right.
For the current value \(a_i\):
- The needed complement is \(y = x - a_i\).
- If we have already seen a value equal to \(y\), we can output the pair.
- Otherwise, store the current value and its index in a map and continue.

Because each element is processed once, and each map operation is \(O(log(n))\), the whole algorithm runs in \(O(n log(n))\) time.

If we finish the loop without finding any pair, the answer is IMPOSSIBLE.

Map idea (online pairing)

For each index \(i\) from \(1\) to \(n\):

Let need = x - a[i].
If need exists in the map with some index j, then:
- We found a solution: a[i] + a[j] = x.
Otherwise, store a[i] with its index i in the map and move on.

We must store original indices and print them as 1-based.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long x;
    cin >> n >> x;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // value -> index (1-based)
    map<long long, int> pos;

    for (int i = 0; i < n; i++) {
        long long need = x - a[i];

        auto it = pos.find(need);
        if (it != pos.end()) {
            // found a pair: a[i] + need = x
            cout << it->second << " " << (i + 1) << "\n";
            return 0;
        }

        // store current value with its 1-based index
        pos[a[i]] = i + 1;
    }

    cout << "IMPOSSIBLE\n";
    return 0;
}

Pitfalls

Distinct positions: using the map of previous elements ensures \(i \neq j\) automatically.
1-based indices: CSES expects positions starting from 1, so remember to print i + 1.
If values repeat, the map will keep the last seen index for that value — which is fine, because any valid pair is acceptable.