Circular Array Rotation: Python 2.7

Question

I am trying to implement a circular rotation algorithm for a hackerrank challenge question. My code(middle block) seems to run fine for small inputs but fails for larger inputs due to timeout. Any help optimizing the code will be much appreciated.

Here is my code:

import sys


n,k,q = raw_input().strip().split(' ')
n,k,q = [int(n),int(k),int(q)]
a = map(int,raw_input().strip().split(' '))

for j in range(0,k):
    temp = a[n-1]
    for i in range(n-2, -1, -1):
        a[i+1] = a[i]
    a[0] = temp    


for a0 in xrange(q):
    m = int(raw_input().strip())
    print a[m]

Consider using numpy.

DYZ
– DYZ

2017-09-06 03:43:24 +00:00
Commented Sep 6, 2017 at 3:43 — DYZ
– DYZ, Commented Sep 6, 2017 at 3:43

Xgh05t · Accepted Answer · 2020-01-11 01:03:12Z

1

You don't have to actually rotate the array to find the item but you can use modulo calculus to do that. If we have index i and we move it k places his new index will be m=(i+k)%n so if we have an index m that has been moved k places then it's previous location was i=(m-k)%n, but since we have to handle it becoming negative if k > m we add len(a), python handles this but in general it's the more complete answer.

Knowing that we can write the following:

for a0 in xrange(q):
    m = int(raw_input().strip())
    prev_index = (len(a) + m - k) % n
    print a[prev_index]

edited Jan 11, 2020 at 1:03

Xgh05t

2403 silver badges11 bronze badges

answered Sep 7, 2017 at 13:49

Tomer Arazy

1,82311 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Circular Array Rotation: Python 2.7

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related