Suppose that there exists an \(M\) satisfying the condition. Let \(X\) be the majority in \(A\) after such operation. Also, let \(S\) be the set of \(i\)’s such that \(A_i \bmod M =X\).

If \(i\) and \(j\) are contained in \(S\), \(A_i \equiv A_j \pmod M\), so \(M\) is a divisor of \(|A_i - A_j|\). By trying all divisors of \(|A_i - A_j|\) at least \(3\), we can obtain a desired \(M\).

Here, choose \(i\) and \(j\) randomly from integers between \(1\) and \(N\). \(i\) and \(j\) are contained in \(S\) at probability at least \(\frac{1}{4}\). Thus, it is sufficient to repeat the randomized step \(\log_{\frac{3}{4}}(1-L)\), where \(L\) is the probability of obtaining the correct answer. Therefore, the problem can be solved in an expected \(\mathrm{O}(\log_{\frac{3}{4}}(1-L) \times N\sqrt{\max A})\) time by the following algorithm. Since the maximum number of divisors less than \(10^9\) is \(1344\), it operates even faster.

If there is no such \(M\), it is sufficient to report that there is no such \(M\) after repeating the randomized step a certain number of times.

If \(U \bmod V =0\) and \(M=U\) satisfies the conditions, so does \(M=V\).

So it is actually sufficient to check not all the divisors of \(|A_i-A_j|\) at least \(3\), but only the prime factors of \(|A_i-A_j|\) other than \(2\), as well as \(4\). In this case, the complexity is \(\mathrm{O}(\log_{\frac{3}{4}}(1-L) \times N\log \max A)\).