Even Modulo Pair

The obvious $O(n^2)$ check is too big if you do it over the whole array. But this problem has a nice little trapdoor: if a sequence has no valid pair, it must be tiny.

We want $x<y$ and:

$$y \bmod x \text{ is even.}$$

Let's understand what a sequence with no such pair would need to satisfy.

Even numbers are dangerous

Suppose there are two even elements $x<y$.

Because $x$ is even, every multiple of $x$ is even. So when computing $y \bmod x$, we subtract an even number from $y$.

Since $y$ is also even, the remainder is even.

So two even numbers always form a valid pair. Therefore, in any sequence with no answer, there can be at most one even number.

Also, if $1$ appears, then for any later element $y$:

$$y \bmod 1 = 0,$$

which is even. So a no-answer sequence of length at least $2$ cannot contain $1$.

Odd numbers must grow stupidly fast

Now take two odd elements $x<y$. Write:

$$y = qx + r,$$

where $r = y \bmod x$.

Since $x$ and $y$ are odd:

• if $q$ is odd, then $qx$ is odd, so $r = y-qx$ is even;
• if $q$ is even, then $qx$ is even, so $r = y-qx$ is odd.

So for odd $x$ and odd $y$, the pair is valid exactly when:

$$\left\lfloor \frac{y}{x} \right\rfloor$$

is odd.

If there is no valid pair, then for every earlier odd $x$ and later odd $y$, this quotient must be even.

Since $y>x$, the quotient is at least $1$. It cannot be $1$, because $1$ is odd. So it must be at least $2$.

That means every later odd number must satisfy:

$$y \ge 2x.$$

But $y$ is odd and $2x$ is even, so actually:

$$y \ge 2x+1.$$

So the odd elements in a no-answer sequence grow at least like this:

$$3, 7, 15, 31, 63, \ldots$$

More formally, if the odd elements are $b_1<b_2<\dots<b_k$, then $b_1\ge 3$ and:

$$b_{i+1} \ge 2b_i+1.$$

This gives:

$$b_i \ge 2^{i+1}-1.$$

Now use the constraint $a_i\le 10^9$.

For $i=29$:

$$2^{30}-1 = 1073741823 > 10^9.$$

So there can be at most $28$ odd numbers in a no-answer sequence.

And there can be at most one even number.

Therefore, any no-answer sequence has length at most:

$$28+1=29.$$

That is the whole trick. If you look at any $30$ elements, there must be a valid pair. No segment tree. No weird DP. Just parity doing its job for once.

Algorithm

For each test case:

1. Let $m=\min(n,30)$.
2. Check every pair among the first $m$ elements.
3. If $a_j \bmod a_i$ is even, print $a_i$ and $a_j$.
4. If no pair is found, print -1.

Why is this enough?

• If $n<30$, we checked every pair in the whole array.
• If $n\ge 30$, then the first $30$ elements must contain a valid pair, by the growth argument above.

So the brute force is tiny but complete.

Complexity

We check at most:

$$\binom{30}{2}=435$$

pairs per test case.

So the complexity is:

$$O(30^2 \cdot t),$$

which is effectively constant per test case and easily fits.