Even Modulo Pair

Throughout my grueling grind on Codeforces, I have stumbled across a few rather interesting problems, and the one mentioned in this article is no exception. The problem, 2164B: Even Modulo Pair features a trivial, yet ingenious solution that taps on one’s understanding in number theory and a little bit of math. When I first read the editorial along with multiple comments and videos, I was baffled as I could not understand the actual theoretical upper bound of the solution. After further reading and experimenting, I finally reached an understanding and I will try to explain my thought process and reasoning in this article.

Problem Statement

The problem statement is direct and straightforward where an important keyword, strictly increasing has been highlighted right off the bat. This is important as it suggests there will be no duplicates with the same value like so: ${a}_{1} < {a}_{2} < {a}_{3} < ... < {a}_{n}$, which is not the be confused with non-decreasing where the opposite applies. The problem requires the selection of two distinct elements $x$ and $y$ such that $x < y$ and $y\ \%\ x == even$.

To achieve this result, there can be only two possibilities: first, both $x$ and $y$ are even; second, both $x$ and $y$ are odd but if and only if $x < y < 2x$. Hold on, I will prove how I derive at this solution later on.

Proof

If the provided array of size $n$ contains all even numbers, then the solution is trivial. One may simply perform a brute-force with doubly-nested for loops to check the numbers against one another, return when two even numbers are found and call it a day as $even\ \%\ even == even$. However, this solution has a quadratic time complexity of $O(n^{2})$ which will certainly lead to TLE as the time limit is 1 second and $n\leq10^{5}$ where $n^{2} = (10^{5})^{2} = 10^{10}$ which is $>10^8$ operations per second of a typical CPU. As such, the algorithm will definitely take more than 1 second to complete…right?

Usually, yup, but with proper bounding, the algorithm can be proven to run within time constraint. Consider this, what if there is no even number in the array? Or, maybe there’s only 1 even number which is insufficient to form a pair. In this case, we’ll have to look for a valid pair of odd numbers. For example, let’s take a look at this sequence with only odd numbers with $n = 5$:

Let $x = 5$, now we need to find another odd number, $y$ such that $y\ \%\ x == even$. Notice that any odd number within the range of $x < y < 2x$ is valid? For example, $9\ \%\ 5 = 4$, $7\ \%\ 5 = 2$. Since $y\ \%\ x = y - floor(\frac{y}{x}) * x$, we can pick an odd number $y$ such that $floor(\frac{y}{x}) = 1$ which will allow for $odd - odd = even$. In order to satisfy the aforementioned criteria, the possible values for $y$ must only exist in the range of $x < y < 2x$. Hence, if odd numbers exist within that range, one can simply pick any of the odd number as $y$ and return along with $x$.

However, if there is no odd number $y$ in $x < y < 2x$, this means that $y > 2x$, so we have to find $y$ in the next range of $2x < y < 4x$. If no odd number exists within that range, then we will proceed with the next range of $4x < y < 8x$, so on and so forth and thus forming the sequence should no odd number exists within each range:

The above sequence shows the worst-case scenario with only odd numbers and no odd numbers exist between the valid range. As a result, each element is $2^i$ times of the first element, or 2 times the previous element where $i$ is the current index of the element in a 0-indexed array. Thus, in a worst-case scenario, $n$ will only be at maximum, 30 as any number afterward will surpass the input constraint of $a\leq10^9$ where $a$ represents each array element as evident in $2^{30} = 1073741824 > 10^9$, which allows for an $O(n^2)$ algorithm to be valid.

Solution in Code

To be honest, I had no clue this would get accepted as I only submitted when I really ran out of ideas. I was wary of the time constraint but after a lot of analysis, I still couldn’t think of a more optimized solution. In the end, it was more about proving why brute-forcing works rather than the implementation of some fancy algorithm. Anyway, here’s my solution in C++:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
  ll n;
  cin >> n;
 
  vector<ll> nums(n);
  for (auto &a : nums) {
    cin >> a;
  }
 
  REP(i, 0, n) {
    REP(j, i + 1, n) {
      debug(nums[i], nums[j]);
      if (nums[i] < nums[j]) {
        if ((nums[j] % nums[i] == 0) || ((nums[j] % nums[i]) % 2 == 0)) {
          cout << nums[i] << ' ' << nums[j] << '\n';
          return;
        }
      }
    }
  }
  cout << -1 << '\n';
}
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

Conclusion

In conclusion, it is proven that the $O(n^2)$ brute-force solution is bounded to $n=30$ which is more than enough to execute the algorithm within the 1 second time limit as required by the problem statement. The time complexity of the algorithm should be roughly $O(n\log V)$ where $V$ is the element with the largest value, or the last index. If $V = 1073741824$, then $\log V = 30$, so for each number in array of size $n$, we only need to check 30 times. Isn’t this a fascinating problem?