Reposting because OP deleted the post.
A number is called valid if digits 2, 4, and 8 occur in it with equal nonzero frequencies. For example, numbers 248, 284824, and 2148 are valid, whereas numbers 3456 (different frequencies) and 356 (zero frequencies) are not. Given an integer 1 <= n <= 10^10, count the number of valid numbers in range [1, n] (inclusive).
Example: n = 300
Output: 2
Explanation: 248 and 284 are the only valid integers in range.Example: n = 1248
Output: 7
Explanation: 248, 284, 428, 482, 824, 842, 1248 are the valid integers in range.This is a digit dp problem. Here is my python solution:
#!/usr/bin/env python3
import functools
class Solution:
def count248Numbers(self, n: int) -> int:
s = [int(d) for d in str(n)]
@functools.cache
def dp(i: int, f: bool, x: int, y: int, z: int) -> int:
# O(log^4 n) states, O(1) transitions per state
if i == len(s):
return x == y == z > 0 # equal nonzero frequencies
if x > 3 or y > 3 or z > 3:
return 0 # pruning to improve the constant factor
return sum(dp(i + 1, f or d < s[i], x + (d == 2), y + (d == 4), z + (d == 8))
for d in range(10) if f or d <= s[i])
return dp(0, False, 0, 0, 0)
def naive(self, n: int) -> int:
# naive O(n log n) implementation for testing
ans = 0
for x in range(n + 1):
s = str(x)
if s.count('2') == s.count('4') == s.count('8') > 0:
ans += 1
return ans
def main():
print(Solution().count248Numbers(int(input())))
if __name__ == '__main__':
# tests
solver = Solution()
for n in (300, 1000, 10000):
assert(solver.naive(n) == solver.count248Numbers(n))
main()Comments (3)