Number of possible palindrome sequences

Here is the problem description from hackerearth.com:


Rohan loves Palindromes. Palindrome is a string that read same forward
and backward. For example abba is a palindrome while abca is not.


Rohan is forming a palindrome of length lesser than or equal to \$n\$,
with first \$k\$ characters of lowercase English letters. He needs your
help to find out the number of possible palindromes.


Output the result modulo \$10^9 + 7\$


Input Format: First line contains 2 space separated integers, \$n\$ and \$k\$


Output Format: Output a single integer, which is answer to the problem


Constraints: \$1 ≤ n ≤ 10^9\$        \$1 ≤ k ≤ 26\$


Sample input:

3 2

Sample Output:

8

I tried making it and it was working fine for some small input but in case of large input its saying time limit exceeded. I think my code running time is \$O(n^2)\$, but I am not sure.

My code:

a,b = raw_input().split()
a = int(a)
b = int(b)
sum = 0
z = b
for i in xrange(1,a+1,2):
    d = z*2
    sum +=d
    z = z*b

if (a+1) % 2 == 0:
    sum = sum - (d/2)
print sum%1000000007

I am interested in knowing that where I am doing wrong with my code and how can I fix this. Also what should I do at first when I face these kind of problem whenever I have to deal with long input because every time I see any time limit error I am not able to fix it.

1. Introduction

You asked:


what should I do at first when I face this kind of problem?

This is a good question! When I studied computing at university I was taught the following general technique:

-
Analyze the program and work out its complexity — that is, how does its runtime depend on its input?

-
Measure its runtime on some small examples.

-
Combine the complexity from step (1) with the measurements from step (2) to estimate the runtime for the worst case.

-
If the worst case is unacceptable, try to find a better algorithm.

As you get better at carrying out these steps, some of them will become second nature to you and so you won't have to go through them all in such detail as I do below. But when you're starting out, or unsure about the approach to take it's good practice to be thorough.

1. Analysis

-
The way to analyze a program is to annotate each line with the time it takes and the number of times it is executed. Then all you have to do is multiply and add!

But that's easier said than done, because how on earth do we know how long each line takes to execute? If we really wanted an accurate answer we could estimate it by running lots of tests. But we don't actually need to compute an exact answer: we just want an idea of how the runtime varies as a function of the input size. So as a first approximation, we'll say that simple operations (assignment, calling xrange, etc) take constant time 1, and that arithmetic operations like addition and subtraction take time proportional to the number of digits in the numbers. (We'll see later that this is an over-simplification, but it will have to do for now.)

CODE                          TIME TAKEN  NUMBER OF EXECUTIONS
============================  ==========  ====================
sum = 0                       1           1
z = k                         1           1
for i in xrange(1, n+1, 2):   1           n / 2
    d = z * 2                 log z       n / 2
    sum += d                  log sum     n / 2
    z = z * k                 log z       n / 2
if (n + 1) % 2 == 0:          log n       1
    sum = sum - d // 2        log sum     0 or 1
r = sum % 1000000007          log sum     1

(Note that I've rewritten the code to use n and k instead of a and b, so that the code more closely matches the statement of the problem.)

Now, in order to turn this into a total runtime, we need to know how big sum and z become. Well, \$z\$ gets multiplied by \$k\$ on each iteration of the loop, so after the \$i\$th iteration, \$z = k^{i+1}\$, and so \$z\$ is no more than about \$k^{n\over 2}\$ and so \$\log z\$ is no more than about \$n \log k \over 2\$.

At each iteration we add \$2z\$ to sum, where \$z\$ is no more than \$k^{n\over 2}\$. And there are about \$n \over 2\$ loop iterations, so sum is no more than \$nk^{n\over 2}\$ and so \$\log{sum}\$ is no more than \${n\log k\over2} + \log n\$. So adding everything up, we get a total runtime bounded by $$1 + 1 + {n\over 2} + {n^2 \log k \over 4} + {n^2 \log k + n\log n \over 2} + {n^2 \log k \over 4} + \log n + 2{n \log k + \log n \over 2}$$ which we can reorganize in terms of \$n\$ to get $$ n^2 \log k + {n\log n\over 2} + (\log k + {1\over 2})n + 2\log n + 2.$$ Now, as \$n\$ gets large, the terms containing \$n^2\$ will dominate (all the other terms become small by comparison). So we expect that as \$n\$ becomes large the runtime will become roughly proportional to \$n^2\log k\$.

(If this looks kind of complicated, it's because I've written out all the steps in detail. When you get experienced with the method, then you can skip all the steps that you know aren't going to appear in the result and just concentrate on the "big guns". For example, I would say to myself, "hmmm, that's \$Θ(n)\$ loops, each of which is handling numbers of typical size \$Θ(n\log k)\$ so the total runtime is \$Θ(n^2\log k)\$.")

-
Measurement is easier if we organize the code into functions, like this:

def palindromes(n, k):
    """Return the number of palindromes up to n letters long, using an
    alphabet of k letters, modulo 1000000007.

    """
    sum = 0
    z = k
    for i in xrange(1, n + 1, 2):
        d = z * 2
        sum += d
        z = z * k
    if (n + 1) % 2 == 0:
        sum = sum - d // 2
    return sum % 1000000007

Now we can measure the time taken (using Python's built-in timeit module) for some small values of \$n\$:

from timeit import timeit

def t(n, k):
    """Return the time taken to compute palindromes(n, k)."""
    return timeit(lambda:palindromes(n, k), number=1)

>>> t(10**3, 26)
0.0003402099828235805
>>> t(10**4, 26)
0.01810335897607729
>>> t(10**5, 26)
1.3598145439755172
>>> t(10**6, 26)
137.12631450797198

-
Let's plot the measurements from step (2) and draw a line of best fit to the equation \$t=an^2\$ that we worked out in step (1):

The fit looks pretty good and the coefficient of proportionality is \$a = 1.37 × 10^{-10}\$.

The worst cas

StackExchange Code Review Q#143342, answer score: 2