You can use a very similar reasoning to the one commonly used to prove Lucas's lemma. The method below is not very short, but I think it's transparent, and it's straightforward to adapt it to trailing zeros in any base $b$ congruent to any remainder
$r$ mod $m$ (10, 0, 2 respectively in our case). You can probably also use it to prove the patterns that the solution you linked exploits.

To get some symmetry, let's define
$$F(n) = \#\left\{ 1 \le j \le n : 2 \mid z(k) \right\} -
\#\left\{ 1 \le j \le n : 2 \nmid z(k) \right\}.$$
The number of even $z$'s up to $n$ can easily be recovered as $\frac{F(n)+n}2$.

Let ${\rm ord}_p(n) = \max \{ t \in \mathbb Z : p^t | n\}$ denote the largest exponent of $p$ that divides $n \in \mathbb N$. Then, an alternative formula for $z$ is:
$$z(n) = \sum_{i=1}^n {{\rm ord}_5(i)},$$
the advantage being that the sequence $({\rm ord}_5(i): i\in \mathbb N)$ is almost periodic in a sense: $({\rm ord}_5(i): 1\le i \le 5^{k+1})$ is the same as $({\rm ord}_5(i): 1\le i \le 5^k)$ five times, except for the last term.

Let's first compute $z(5^k)$ and $F(5^k)$ inductively (actually, we only care about $z$ mod $2$).

$$z(5^{k+1}) = 5\cdot z(5^k) + 1$$
$$F(5^{k+1}) = \left( 3+2\cdot(-1)^{z(5^k)} \right)\cdot F(5^k) + 2\cdot(-1)^{z(5^{k+1})}$$

Similarly, for $1 \le d < 5$:

$$z(d\cdot 5^k) = d\cdot z(5^k)$$
$$F(d\cdot 5^k) = \left( \left \lceil{\frac d 2}\right \rceil
+ \left \lfloor{\frac d 2}\right \rfloor \cdot(-1)^{z(5^k)} \right) \cdot F(5^k)$$

Finally, note that if $0 < b < 5^k$ and $5^k | a$, then
$$ z(a+b) = z(a) + z(b) $$
$$ F(a+b) = F(a) + F(b)\cdot(-1)^{z(a)} $$

If your number in base 5 is $n = \overline{ d_{k-1}d_{k-2}\dots d_0 } _{(5)}$, then this allows you to iteratively compute $F\left(\overline{ d_{k-1}d_{k-2}\dots d_{k-j}00\dots0 } _{(5)} \right)$ for $1 \le j \le k$, all in $O(k) = O(\log n)$ steps. (That is, if you assume that $F(j)$ will fit in a constant precision integer. As $F(i) = O(i)$, I think the real asymptotic runtime is $O(\log^2 n)$ for truly large values of $n$).