# Rotated Digits

It's working now. Thank you!

• Dear awice, I am really impressed by the second solution. The code is very solid, though I do not quite agree with your verbal definition of the 3rd dimension:

I think the third dimension should be defined as:

• `0`: we must have at least one 2569 in `[i:]`.
• `1`: we may have one 2569 in `[i:]`.

as we can see from the code:

• if `invo` is 0, which means we are not adding a 2569 at digit `i`
• If `invf` is 0, the code shows we look at `[i+1][..][0]`. That means, we are trying to count good numbers in `[i:]` that must have at least one 2569, that's why we need to look back at `[i+1][..][0]`, because we don't have one inv digit at `i`, we have to count on `[i+1:]` to provide one.
• If `invf` is 1, then code shows we look at `[i+1][..][1]`. That means, we are trying to count good numbers in `[i:]` with maybe one 2569. We did not provide one at `i` because `invo = 0`, but it doesn't matter, because we are not mandated by anything. Look at how many good numbers are in `[i+1:]` that may have 2569.
• if `invo` is 1, which means we are providing an inv digit of 2569 at `i`. Then we surely should be looking back at `[i+1][..][1]` because we provided one 2569 at `i`, and now it doesn't matter what `invf` is (meaning whether we require there must or may be 2569 in `[i:]`) because we got one.

And to better explain the initialization of `[K][..][1] = 1` and `[K][..][0] = 0`, I modify the definition of the second dimension as well:

• The second dimension corresponds to whether, the counted numbers included in this `memo` cell, must be less or equal to the corresponding `[K:]` of the given number `N`.

This is an intuitive interpretation, because, at termination, we only care about `[0][1][0]` with the second dimension being `1`: meaning we only count those numbers that are less or equal to `N`.

Coming back to the initialization, why is it that the init is only determined by `invf`? Because talking about `[K:]`, it's empty. Any number we build from digits `[K:]` of `N` will be satisfying the less or equal condition. That's why `eqf` does not matter at all during initialization. Since the definition of `invf = 1` indicates a may contain 2569, and we sure have to set those cells to 1 because does not contain belongs to may contain.

Here is a helpful illustration of the first iteration. Be aware of the inversed `eqf` dimension: I apologize for that:

• 1st solution is overcomplicated

`(d not in '347' for d in S)` and `(d in '2569' for d in S)` are too expensive

Below is 2x faster

A good number is a number which has none of bad digits( {3,4,7} ) and at least one good digit( {2,5,6,9} }

``````    bad = ['3', '4', '7']
good = ['2', '5', '6', '9']

ans = 0
for i in map( str, range( 1, N + 1 )):
to_continue = True
if k in i:
to_continue = False
break
if to_continue:
for k in good:
if k in i:
ans += 1
break
return ans``````

• I think or the brute once solution
the python code should be
if any (d in '2569' for d in S) and all (d not in "347" for d in S):
ans += 1

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.