Problem SPOJ - Even Count TLE

any idea what to do to make it small…
precomputing values till 10^6 also nt wrkin for 10^9 elements

1 Like

Well this is pretty classic problem.

Firstly imagine we want to count number of values i such as f(i) is even and 1 <= i <= R. Now for original problem for L, R answer will be sol®-sol(L-1). This only help to avoid problems with boundaries.

Secondly let’s say that R=(10^k)-1 so we have got all numbers with at most k digits. We know that product of digits will be even if at least one of digits is even. Now let’s crete all numbers with k digits (also they can begin with 0). If we add even (and bigger than 0) digit on begining of this number the f(x) for all numbers starting with this digit will be even, so we can add 10^k-1 to final result and that’s all. If we start with 0 or odd number, the even digit must be in remaining k-1 digits. So we can use recursive call and add number of solution for R=(10^(k-1))-1.

Last step, our R isn’t that nice. But we can use similar approach. For example R=5241. First digit can be 0, 1, 2, 3, 4, or 5. If first digit is 2 or 4 we add 999 to times to result (all numbers with 4 digits starting with 2 and with 4). If first digit is 0, 1 or 3, we use recursion on R=999 (even number is in remaining 3 digits). Now if we choose as first number 5, we cannot use recursion with R=999 because we would add also number 5823 to solution as well and that’s not correct. But we can use recursion with R=241. Now everything will be fine. Also notice, if our original R begins with even digit, for example R=82474 we add all remaining numbers so 2474 to result.

Now you should know how to solve it. If you have any troubles just ask. Also you may use (or maybe must) use memoization in your recursion calls.

1 Like

sir sorry but didn’t get your example(last para),

you mean, when R=5241?

yes sir…
little more explanation required