Challenge lab in Hash Tables and Collision Reasoning

Mission

Decide whether two distinct input positions sum to target.

Learning outcome: Design a one-pass complement lookup

Correctness contract

Invariant: Equal keys produce equal hashes, and collision handling preserves every distinct key.

Required technique: Scan once with a set of prior values, checking target - value before adding the current value.

Complexity target: time O(n) average; space O(n).

Input and output

Input: n, then n integers, then one target integer. Whitespace may be spaces or line breaks.

Output: Print exactly true or false in lowercase. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• n is positive and all values and the target fit in signed 32-bit storage.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Scan once with a set of prior values, checking target - value before adding the current value.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

4 2 7 11 15 9

Sample output

true

Why the sample works: Visible walkthrough for the ordinary non-trivial path. For each value, the set of earlier values is checked for its required complement before the current value is added. Input `4 2 7 11 15 9` therefore produces `true`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Checking before insertion is what prevents one array position from pairing with itself.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.