You are viewing a single comment's thread. Return to all comments →
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 .
print sum([a * b for (a, b) in zip(sum_count, unhappy)]) % (int(1e9) + 7)