Valid 248 Numbers
Accenture coding challenges question, verified with a worked answer. Free to practise - no sign-up.
A number is called valid if the 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 n, count the number of valid numbers in the range [1, n] (inclusive).
Input format
A single integer n.
Output format
A single integer representing the count of valid numbers.
Constraints
1 <= n <= 10^10
Sample tests
Sample 1
Input
300
Expected
2Sample 2
Input
1248
Expected
7Show a reference solution
Reference solution
def count_248_numbers(n):
s = str(n)
memo = {}
def dp(idx, is_less, is_started, c2, c4, c8):
if idx == len(s):
return 1 if is_started and c2 == c4 == c8 and c2 > 0 else 0
state = (idx, is_less, is_started, c2, c4, c8)
if state in memo:
return memo[state]
limit = 9 if is_less else int(s[idx])
ans = 0
for d in range(limit + 1):
if not is_started and d == 0:
ans += dp(idx + 1, True, False, 0, 0, 0)
else:
nc2 = c2 + 1 if d == 2 else c2
nc4 = c4 + 1 if d == 4 else c4
nc8 = c8 + 1 if d == 8 else c8
if nc2 <= 3 and nc4 <= 3 and nc8 <= 3:
ans += dp(idx + 1, is_less or (d < limit), True, nc2, nc4, nc8)
memo[state] = ans
return ans
return dp(0, False, False, 0, 0, 0)