We should try to think the reverse solution. For eg. we have to get 89 using squares of numbers (1-9). Obtain 89 using 1, 4, 9, 16, 25, 36, 49, 64, 81 once or more than once. eg. 4+4+81=89 (the numbers are permutations of 2,9,2,0,0,0,0,0,0,0) use recursion and count

Not that easy.

I have one idea in mind that would lower the complexity, but I don't think it'll lower it enough.

I am thinking to reformulate numbers under the following forms:

(number) = a*1 + b*2 + ... i*9

In other words, what really matters is the number of times each digit is repeated. So every number between 1 - 10^K can be reformulated as such. Many numbers in there will in fact be just reformulation of the same pattern (e.g. 227788, 728827, etc are identical "paths" to 89 or to 1).

So the problems then becomes about elaborating each combinaisons (keeping in mind we have at most: a + b + ... i <= 200), figuring out if it leads to 89 or 1. This is still a lot (around 22^9, or 1.2 trillions) though...

There has to be a mathematical pattern, but can't find it yet....

I am getting time out after three test cases? any help.Is there any specific pattern in happy numbers and unhappy numbers(two types of numbers mentioned in the problem)

It's funny how Pypy can pass in 0.88s while Python 2 could exceed 10s. By the way, very hardcore dynamic programming practice. Recursive DP is not something I've been used to.

EDIT: An iterative DP approach considering the number of occurrences of square digit sum within k digits, is in my opinion, much easier to comprehend, without heavy usage of global variables and fear of recursion limit.

It can also pass all test cases in Python 2. The last line of this implementation is: print sum([a * b for (a, b) in zip(sum_count, unhappy)]) % (int(1e9) + 7). You may want to generate the list of unhappy numbers (those within the loop) from to .

Would it not be better to explain that : f(n)= sum(sqirt(i) for i in string(n)) is an injection from 10**x space to x*81 space. so for K=200 it means 16281 in term of space. going from 10*x to 10*(x+1) is adding a square (1,4,9,16..81) to {f(10**x)}, so for every cycle it costs at mosts 162810 additions. you get 5*10*7 ops, instead of 10*200; Well good luck to anyone