at
1
1 1
your output is (1,1) , It should be (1,0 ), because we are not doing any operation here , number itself is the minimum one.
I hope it will help you
@sm1dash (sorry, I donât have enough rep points to comment directly below your post) â
Your code ( Link ) doesnât actually traverse a tree, which is the essential requirement to solve the problem.
Hereâs the key section, lines 32-41 and 46:
dval=n;
while (dval > 9)
{
dval=digitSum(dval);
op2++;
}
if (!result[dval])
{
result[dval]=op+op2;
}
...
n += d;
As you know, the while loop takes the current value of n and iterates digitSum() repeatedly until a value <= 9 is found. Then if you havenât already come across that value (i.e. if !result[dval]), you store the number of steps. Then in line 46 you increase n by d and continue to the next pass in the loop.
The problem is that digitSum(n + k ¡ d) (for some k, 0â¤kâ¤9) is not always the shortest solution, which is why a binary tree is needed. At each fork point, your options are to add d to the current value, or apply digitSum() to the current value. This leads to 2^x possibilities, where x is max-number-of-steps. Your loop just covers 10 possibilities.
In the editorial itâs mentioned that the relative order of the add and sumofdigit() operations does matter! Could you please give me one testcase where this matters? My code didnât take this into account and thus i failed 4 out of 8 tasks â CodeChef: Practical coding for everyone
what is it with 2047. I read a few codes of people and many have used i<2047. Can anyone please tell me. Like in this solution:
CodeChef: Practical coding for everyone (this is not my code)
Btw Isnât time complexity of / and % logn. Does faster than method extended gcd or binary search exist ?
For large integers youâre right. Large integer division in python for example has complexity is something like O(\log{n}^2). For small integers (in this context 32-bit or 64-bit numbers) we can view this as a constant cost (albeit expensive compared to addition or multiplication). In this case we have comparatively small (10^10 fits easily into 64-bits) numbers.
I also wanted to know. Opened your soln but was unable to understand.
@vivek_1998299 I wonât go into full detail here. The Berlekamp-Massey algorithm can be used to find the shortest linear feedback shift register that fits a sequence. For this purpose, think of finding k coefficients c_i of a relation a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{a-k} such that the relation recreates a given sequence. When the sequence has been found you can rather quickly find the nth term.
So essentially, simulate for a bit, throw the result into Berlekamp-Massey and extrapolate. Here I ignore some pitfalls, but itâs the essential idea.
made some changes, thanx
woooohâŚnice
Digital root is not just n \bmod{9}, see my answer MINDSUM - Editorial - #5 by algmyr - editorial - CodeChef Discuss