$f_n(x) = 0$ exactly when $|x - n|$ is a nonnegative zero of $f_{n-1}.$ Compute the zero sets for the first few $n.$

With $T_k = \frac{k(k+1)}{2},$ the zeros of $f_n$ are every other integer from $n - T_{n-1}$ up to $T_n,$ so their sum is $n\left(1 + \frac{n(n-1)}{2}\right)$

Since $f_n(x) = f_{n-1}(|x - n|),$ the zeros of $f_n$ are exactly $x = n \pm z$ as $z$ runs over the nonnegative zeros of $f_{n-1}.$ The first few zero sets are $\{1\},$ $\{1, 3\},$ $\{0, 2, 4, 6\},$ $\{-2, 0, 2, \ldots, 10\}.$ Writing $T_k = \frac{k(k+1)}{2},$ we claim the zeros of $f_n$ are every other integer from $n - T_{n-1}$ through $T_n.$ Indeed, by induction the nonnegative zeros of $f_{n-1}$ are every other integer from $0$ or $1$ up to $T_{n-1},$ and applying $n \pm z$ yields every integer of the appropriate parity from $n - T_{n-1}$ through $n + T_{n-1} = T_n.$

This progression has $\frac{T_n + T_{n-1} - n}{2} + 1 = \frac{n(n-1)}{2} + 1$ terms, and its first and last terms sum to $(n - T_{n-1}) + T_n = 2n,$ so the sum of the zeros is $$S_n = n\left(\frac{n(n-1)}{2} + 1\right),$$ which is increasing in $n.$

Now $S_{100} = 100 \cdot 4951$ $= 495{,}100 \le 500{,}000,$ while $S_{101} = 101 \cdot 5051$ $= 510{,}151 \gt 500{,}000.$ The least such $n$ is $101.$