Circular Array Rotation My code works fine, but it's takes too much time, say around 65 seconds, for large input data. If there are 50,000 numbers in the list \$a\$ and we have to rotate the numbers 45,000 times then it takes 1 minute.

How can I reduce the time it takes to print all the numbers?

Problem:
perform an operation called a right circular rotation on an array of integers [a0 , a1 , a2 , ..a(n-1)]. After performing one right circular rotation operation, the array is transformed to [a(n-1) , a0 , a1 ,..a(n-2)].

Input Format


The first line contains 3 space-separated integers, \$n\$, \$k\$ 
and \$q\$ respectively.
The second line contains \$n\$ space-separated integers, where each
integer \$i\$ describes array element a[i] (where \$0 \le i&lt;n\$).
Each of the \$q\$ subsequent lines contains a single integer denoting \$m\$.




n,k,q = input().strip().split(' ') #n=no of integers in the list , k=no of rotation ,q=no of lines for integer m

n,k,q = [int(n),int(k),int(q)] 
a = [int(a_temp) for a_temp in input().strip().split(' ')]

for i in range(0,k):   
    a=[a.pop(n-1)]+a  #for putting the last element to the first position and del it from the last pos

for a0 in range(q):    # printing value of a at a given index
  m = int(input().strip())           
  print(a[m])


Sample Input

3 2 3
1 2 3
0
1
2


Sample Output

2
3
1


Explanation


After the first rotation, the array becomes [3, 1, 2].
After the second (and final) rotation, the array becomes [2, 3, 1].
Let's refer to the array's final state as array \$b\$. For each query, we
just have to print the value of b[m] on a new line:
\$m=0\$, so we print \$2\$ on a new line.
\$m=1\$, so we print \$3\$ on a new line.
\$m=2\$, so we print \$1\$ on a new line.
You can change your array packing to use map instead.

n, k, q = map(int, input().strip().split(' '))

When popping the last element you don't need to pass an argument.
Rather than popping each element, you can perform two slices and an addition. You would also have to use the modulo operator, %, for when \$k \ge n\$.

k %= n
a = a[-k:] + a[:-k]

You don't need to strip a number, as int will do this for you.


This can get you:

n, k, q = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
a = a[-k:] + a[:-k]
for _ in range(q):
    print(a[int(input()])


If you however want some sugar you can use collections.deque, it comes with deque.rotate that can perform the rotation in (3) for you. which can result in:

from collections import deque

n, k, q = map(int, input().strip().split(' '))
a = deque(map(int, input().strip().split(' ')))
a.rotate(k)
for _ in range(q):
    print(a[int(input()])


The above is good enough for the hackerrank challenge, however performs worse than the code above it. Rotating the array is \$O(n)\$, where the deque is \$O(k)\$. But indexing the array is \$O(1)\$, where the deque is \$O(n)\$. This means the first code block is \$O(n + q)\$ and the second is \$O(k + nq)\$. To make the second \$O(n + q)\$ all you need to do is change it to an array before the for loop, via list.



whenever you profile code, you should always take more than one timing, with more than one input. Hai Vu done neither of these.
Using my wrapper to timeit, I wrote some code to profile; deque (Peilonrayz), adding slices (mkrieger), and deleting a slice (Hai Vu), as these are the fastest functions.
However to keep things unbiased I've made a couple of adjustments:


All code will be a Python function in __main__.
All functions work correctly with any \$k\$ and when \$n \ne 0\$. (I use % to do this.)
I run each function 10000 times per timeit.
I run each timeit 10 times, and take the average and interquartile range.


This should give each and every function call the same amount of overhead.
Here is the code that I use to time the functions.

from collections import deque

from graphtimer import time, GraphTimer, flat, time
import matplotlib.pyplot as plt

def mkrieger(a, k):
    k %= len(a)
    return a[-k:] + a[:-k]

def peilonrayz(a, k):
    a = deque(a)
    a.rotate(k)
    return a

def hai_vu(a, k):
    k %= len(a)
    b = a[-k:]
    del a[-k:]
    a[0:0] = b

class Timer(GraphTimer):
    functions = [
        'mkrieger',
        'peilonrayz',
        'hai_vu',
    ]
    inputs = [
        'a = list(range(100)); k = {}'
    ]
    domain = range(1, 101, 1)
    titles = [
        '100'
    ]

if __name__ == '__main__':
    fig, axs = plt.subplots(nrows=1, ncols=1, sharex=True)
    Timer(amount=10, number=10000, stmt='fn(a, k)').plot_axes(flat(axs), show_titles=True)
    plt.show()


Which outputs: