 # Fall for Code Problem A Gandhian Series

In the problem Gandhian Series…my code’s complexity is O(T*k) I guess which is feasible to solve the problem still it is showing TLE
https://www.codechef.com/viewsolution/26910067
Please have a look at this
I know that problems of this type where we have to get the summation of 1^k + …+ 2^k
we have to do them in O(k)
still TLE…Why help!!!

1 Like
``````    m = k + 1
for i in range(2, m):
temp = 0
for j in range(0, i):
temp -= binom(i + 1, j) * S[j]
temp %= p
# print(temp)
temp -= (1 - (n + 1) ** (i + 1))
``````

These bits are your problem. The inner loop has complexity O(k^2) and the raising n to a silly power in total is O(k log(k)) before considering the length of things we’re multiplying (up to 12000 digits which is probably slower than the O(k^2) operation for the choices of parameters we’re interested in).

how to solve this problem? means how to find sum of series (1^k + 2^k + … + n^k) in o(K)?

it is given here in the editorial

1 Like

1 Like

I have updated the test files. Previously it was only changed for contest page. I have now changed it for both. Thanks for reminding. Sorry for the inconvenience caused! 