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.

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