Rotated Digits


  • 1

    Click here to see the full article post


  • 0
    K

    I'm getting a "Page Not Found" when I click the link ^^^

    It's working now. Thank you!


  • 0

    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:


  • 0
    4

    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
            for k in bad:
                if k in i:
                    to_continue = False
                    break
            if to_continue:
                for k in good:
                    if k in i:
                        ans += 1
                        break
        return ans

  • 0
    L

    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


Log in to reply
 

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