Project Euler Problem 95 Statement
Solution
HackerRank version
Given a set of $m$ distinct digits, $S$ , find the largest possible integer $n$ such that each integer from $1$ to $n$ is expressible using elements of $S$ and following the above rules. If $1$ is also not expressible, output $0$ instead.
Python Source Code
# Constants
M = 1000000007 # Modulo value
L = int(input()) # Input limit
C = 81*L + 1 # Max possible sum (9^2*length + 1)
# Set of all squared digits (0^2 to 9^2)
S = {i*i for i in range(10)}
# Recursive check if number is unhappy (ends in 89 cycle)
d = lambda n: n>1 and (n==89 or d(sum(int(c)**2 for c in str(n))))
# Initialize array with base cases (single digit squares)
p = [1 if i in S else 0 for i in range(C)]
# Dynamic programming: build solutions for increasing lengths
for _ in range(L-1):
p = [sum(p[j-s] for s in S if j>=s)%M for j in range(C)]
# Sum all combinations that lead to unhappy numbers
print(sum(v for i,v in enumerate(p) if i and d(i))%M)