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)

can anyone explain me the question what it wants.i didn't understand it

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 .