Because I got frustrated with the problem, I made a dictionary of all digits whose chain of square of digits reaches 1 which can be found in this OEIS link for numbers upto 200 and then return:

print((10**k-(d[k]%MOD))%MOD)

You can also read about happy numbers on wikipedia

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

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

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