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<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.
share|improve this question

Instead of rotating the list \$k\$ times by one position, rotate it by \$k\$ positions in a single step.

In Python, this can be done by simple slice operations:

def rotate(a, k):
    """Rotate a by k positions to the right.

    >>> rotate([1, 2, 3], 1)
    [3, 1, 2]
    >>> rotate([0, 1, 2, 3, 4], -2)
    [2, 3, 4, 0, 1]
    """
    r = k % len(a)
    return a[-r:] + a[:-r]
  • a[-r:] are the last r items of a.
  • a[:-r] are all but the last r items of a.

Note that by taking \$k\$ modulo the length of a, values of \$k\$ outside the range \$0, \dots, n-1\$ will also work.

share|improve this answer
  1. You can change your array packing to use map instead.

    n, k, q = map(int, input().strip().split(' '))
    
  2. When popping the last element you don't need to pass an argument.

  3. 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]
    
  4. 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.

share|improve this answer
    
k=k % len(a) should also be there ,in case no of rotation exceeds the length of the list a. – Kriti Sahu 10 hours ago
    
@KritiSahu Yeah that's right, I didn't check for out of bound data. Just makes me want to use deque even more, ;P – Peilonrayz 9 hours ago
    
but can i import this python module in spoj idle or in hackkerrank? – Kriti Sahu 9 hours ago
    
@KritiSahu I don't know about spoj, but it wouldn't be a good IDLE if you couldn't. As for hackkerrank, I did, and it got me +20. – Peilonrayz 9 hours ago
    
@KritiSahu You can import all the modules in the (3.6) stdlib, except secrets, turtle, tkinter, tkinter.ttk, tkinter.tix, tkinter.scrolledtext, typing, ensurepip, zipapp, msilib, msvcrt, winreg, and winsound. – Peilonrayz 8 hours ago

My first attempt is to do a loop k times, each time rotate one element of the list in place:

for _ in range(k):
    a.insert(0, a.pop()]

This turns out to be slightly better than the original poster (OP) Kriti Sahu's solution (we will see timing numbers later). However, my solution was far worse than other answers here.

Next up, I moved the last k elements to the beginning of the list in place (none of my solution creates a new array, all done in place--the key to performance):

b = a[-k:]  # Save off the last k elements
del a[-k:]  # Delete the last k elements
a[0:0] = b  # Insert to the front

This turns out to be the best timing so far. Here is a little script I wrote to compare solutions I see so far:

import timeit

def time_and_report(expression, setup, header):
    print '{}: {}'.format(header, expression)
    timing = timeit.timeit(stmt=expression, setup=setup)
    print '{} second(s)\n'.format(timing)

#
# Setup
#
array_size = 100
number_of_rotations = 10
setup = 'a=range({array_size}); k={number_of_rotations}'.format(**locals())
deque_setup = 'from collections import deque;' + setup
mkrieger1_setup = """
def rotate(a, k):
    r = k % len(a);
    return a[-r:] + a[:-r]
""" + setup

#
# Compare timings
#
time_and_report('for _ in range(k): a.insert(0, a.pop())', setup, 'Hai 1')
time_and_report('b = a[-k:]; del a[-k:]; a[0:0] = b', setup, 'Hai 2')
time_and_report('a = a[-k:] + a[:-k]', setup, 'Peilonrayz 1')
time_and_report('a = deque(a); a.rotate(k)', deque_setup, 'Peilonrayz 2')
time_and_report('a = rotate(a, k)', mkrieger1_setup, 'mkrieger1')
time_and_report('a = [a[(i+k) % len(a)] for i in range(0, len(a))]', setup, 'Andi Kleve')
time_and_report('for _ in range(k): a=[a.pop()]+a', setup, 'Original')

And here is the output of my timing tests for array of 100 elements:

Hai 1: for _ in range(k): a.insert(0, a.pop())
6.80668497086 second(s)

Hai 2: b = a[-k:]; del a[-k:]; a[0:0] = b
0.700757980347 second(s)

Peilonrayz 1: a = a[-k:] + a[:-k]
1.20484399796 second(s)

Peilonrayz 2: a = deque(a); a.rotate(k)
1.6975209713 second(s)

mkrieger1: a = rotate(a, k)
1.62001395226 second(s)

Andi Kleve: a = [a[(i+k) % len(a)] for i in range(0, len(a))]
39.2207920551 second(s)

Original: for _ in range(k): a=[a.pop()]+a
8.81602191925 second(s)

A Few Notes

  • The deque solution turns out to be worse than the list solution because the overhead of turning a list into a deque
  • When performance is important, operate the list in place will be faster than creating a new list
  • Andi Kleve's solution it much worse than that of the OP
share|improve this answer

Don't rotate the array by copying - that is costly. Simply modify how you access the elements: the result of the N-th rotation can be output as follows (here N=2 as example):

a = range(0,5)
N = 2
[a[(i+N) % len(a)] for i in range(0, len(a))]
share|improve this answer
    
This is incorrect: by rotating 2 times, I expect [3, 4, 0, 1, 2], but got [2, 3, 4, 0, 1] -- it seems you are rotating the wrong direction. Also, see my post for your timing. – Hai Vu 5 hours ago

Put the elements in the shifted position directly removing the need to shift completely:

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int n; 
    int k; 
    int q; 
    scanf("%d %d %d",&n,&k,&q);
    int *a = malloc(sizeof(int) * n);
    for(int a_i = 0; a_i < n; a_i++){

        int la=floor((k+a_i)/n); 

       int j=a_i+k-la*n;
               scanf("%d",&a[j]);          
    }
    for(int a0 = 0; a0 < q; a0++){
        int m; 
        scanf("%d",&m);
       printf("%d\n",a[m]);
    }
    return 0;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.