Original proposer: vwxyz

Let \((A'_1,A'_2,\dots,A'_N)\) be the resulting \(A\).
Once \(A'_1 \pmod{M}\) is fixed, \(A'_i \pmod{M}\) are all uniquely determined.
The minimum number of operations required to turn \(A_i\) into \(A'_i\) equals \((A'_i-A_i) \pmod M\), so the total number of operations required can be computed too.
Since \(M=2\), \(A'_1\) can take two values, \(0\) or \(1\).
Trying both of them and finding the smaller runs fast enough.
The total time complexity is \(O(NM)\).