Digits Alternate Parity — Solution & Editorial

Back to the Problem

Digit DP with prefix difference f(R) − f(L−1), carrying a tight flag and a leading-zero flag.

Complexity: O(digits · states)

Watch out: Encode 'no previous parity yet' as a distinct state (2) so the first digit is unconstrained.