# PROBLEM LINK:

# DIFFICULTY:

SIMPLE

# PREREQUISITES:

# PROBLEM:

You are given an array A of N distinct integers. You are also given an array B of N-1 distinct integers. Determine the smallest possible **positive integer** X such that B_i-X exists in A, for all valid i.

It is guaranteed that X exists.

# EXPLANATION:

Sort A and B. Then A_1 is the smallest element of A, and A_N the largest. Similarly with B too.

**Claim:** X is either B_1-A_1 or B_1-A_2.

## Proof

Since array B was generated using N-1 elements of A, exactly one element of A was left out. Therefore, at least one of \{A_1,A_2\} was selected to generate array B.

Say A_1 was selected. Since X was added to each selected term to create array B, A_1+X is still the smallest term, corresponding to the smallest term in B. Thus A_1+X=B_1 implies X=B_1-A_1.

A similar argument can be made for when *only* A_2 is selected.

All that remains now is to set X to each of the two possible values and validate if B_i-X exists in A, for all i. This can be done efficiently using hash tables.

If both values are possible, select the **smallest positive** value of the two.

# TIME COMPLEXITY:

Sorting A and B takes O(N\log N) each. Checking if B_i-X exists in array A, for all i, takes O(N) using hash tables.

The total time complexity per test case is thus:

# SOLUTIONS:

Editorialistâ€™s solution can be found here

**Experimental:** For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

- 1
- 2
- 3
- 4
- 5

0 voters