Project Euler #92: Square digit chains
Project Euler #92: Square digit chains
+ 0 comments can anyone explain me the question what it wants.i didn't understand it
+ 0 comments 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
+ 0 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 .
+ 0 comments 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
Sort 14 Discussions, By:
Please Login in order to post a comment