rotated digits

← 🏠

https://leetcode.com/problems/rotated-digits/submissions/

Runtime: 60 ms, faster than 82.52% of Python3 online submissions for Rotated Digits.
Memory Usage: 14.7 MB, less than 100.00% of Python3 online submissions for Rotated Digits.

 1from functools import lru_cache
 2
 3good_numbers = set([2,5,6,9])
 4invalid = set([3,4,7])
 5
 6@lru_cache(None)
 7def good(n):
 8    if n < 10:
 9        return int(n in good_numbers)
10    v, r = divmod(n, 10)
11    return good(v) or good(r)
12
13@lru_cache(None)
14def not_invalid(n):
15    return True if n == 0 else n%10 not in invalid and not_invalid(n//10)
16
17class Solution:
18    def rotatedDigits(self, N: int) -> int:
19        return sum(not_invalid(x) and good(x) for x in range(1, N+1))