Numbers with Even Number of Zeros

Fix the definition before counting

Ask whether the task counts integers in a range, binary strings, decimal representations, or numbers with exactly versus at least an even number of zero digits. Confirm whether leading zeros are ignored and how the number 0 is represented. These details change the answer materially. For a small range, scan each canonical representation and count zero characters in O(range * digits) time.

For a large upper bound, use digit DP with state (position, tight, started, parity). Flip parity only when a real digit zero is placed after the number has started; handle the all-zero number separately according to the contract. Memoize non-tight states, giving O(digits * 2 * 2 * 2 * 10) time and small space. Test bounds around 0, powers of ten, and numbers like 1001. Do not silently count padding zeros introduced by fixed-width DP, and do not assume decimal if the interviewer says binary.