FranckV 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....
Deciph3r see i get one interesting thing, that if we generate all numbers which is <16400 or 1e6 into a set S than for higher numbers say 1e50 we have to just check sum of sq. of digits using your method, if its falling into the set or not;
but i think thats too a time consuming job or not? :(
droidian 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)
advancedxy You shouldn't check every number under 10^k, when k >= 8, It's almost certain you program will time out. Think about another way to solve this problem, something dp....
popo same here!!
welcometors Try a different approach. You can compute for K=1000 in a blink of an eye with correct approach.
vb6101993 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
kitchent 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 .
padeff 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
SunilkumarDSK Please explain me the example test case. The Test Case 0. How input=1 and output=7?
Ufush Input indicates number K. When input is 1, you need to check all numbers under 10^1. So there are 7 numbers match the defined criteria among [1, 2, ... 10]
FranckV Is it possible to access the test cases? For other exercises we could, is it possible here? My program gets runtime error only for the last 3 or 4 cases, the others are passing... Difficult to debug without knowing more.
amazinghacker The contest is infinitely long. So, you can never access the solutions or even test cases.
MrAsimov very large numbers are involved. can this be done in C language
NiakTheWizard A proper algo for this problem doesn't require handling big integers (32-bit int are sufficient). This can be done in any language.
ASHWIN_18 TBH anything and everything can be done in C. period
mj123 can someone please explain me the question ??.....what does it meant by print modulo(10^9 +7).....also please explain the first test case!!!!
sudheesh001Asked to answer Hi mj123, Lets take the following example 85→89→145→42→20→4→16→37→58→89
The number 85 has 82+52 = 64+25 = 89
Similarly 89 has 82+92=64+81=145
In the same way 145 gives 12+42+52 = 42
Then 42+22=20
Using 20, 22+02=4
42 = 16
and so on.I hope you can solve it now. printing the modulo means, if the answer you get is N print the value of N%1000000007
eg. 20%1000000007 = 20
1000000047%1000000007=40
Sort 12 Discussions, By:
Please Login in order to post a comment