Algorithm thinking · pairs

Two-Sum Exists

The classic interview warm-up. Loop i over every element, loop j from i+1 so you never pair a number with itself, and check a[i] + a[j] == T.

At a glanceLoop i over every element and j from i+1 so a number is never paired with itself; any pair that sums to T prints yes, and the double loop is fast enough for N ≤ 100.

Problem

Input: first line N (1 ≤ N ≤ 100); second line N integers; third line the target T.

Output: yes if some two distinct numbers sum to T, else no.

Samples:

Input	Output
`4 1 2 3 4 5`	`yes`
`3 1 2 3 7`	`no`
`5 10 20 30 40 50 60`	`yes`

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — distinct, not just different values

Use two indices i and j with j > i. That guarantees two different positions — so [3, 3] with target 6 still counts (positions differ), which is usually what these problems mean by "two numbers".

Hint 2 — stop as soon as you know

You don't need every pair — the moment one match is found, print yes and you're done. If the loops finish with no match, print no. A bool flag avoids re-printing.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int n, t;
    cin >> n;
    int a[105];
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> t;
    bool ok = false;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] == t) ok = true;
    cout << (ok ? "yes" : "no") << endl;
    return 0;
}

Real interviews ask for the indices, or want O(N) with a hash set — but the O(N²) version is the foundation. Next: Second Largest keeps the same "track values while scanning" idea.

Deep dive

Why this works

The pair search is the smallest complete example of "try every combination": two indices, one inequality to keep them distinct, one comparison. Every O(N²) algorithm you meet later is this shape scaled up.

The cost

O(N²) time (10,000 checks at N=100 — instant), O(N) space for the array. The early exit can stop on the first hit, but the worst case is still a full scan.

Where it goes wrong

Looping j from 0 instead of i+1 lets an element pair with itself — [5] with target 10 would answer yes for a single element.
Printing inside the loop: you get yes several times (or yes then nothing) and the judge rejects the output.

Next step

Ask for the indices instead of yes/no, then sort and use two pointers — the same problem in O(N log N). Second Largest keeps the "track while scanning" habit.

Two things to remember

j starts at i+1: distinct positions, never the same element twice.
Decide, then print once — printing inside a search loop multiplies output.

🐞 This version fails — open it and try

Prints inside the loop — several yes lines, and nothing at all for the no cases

#include <iostream>
using namespace std;

int main() {
    int n, t;
    cin >> n;
    int a[105];
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> t;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] == t) cout << "yes" << endl;   // prints per match
    return 0;
}