Optimize program for array rotation

Question

My code is taking too long to execute. Can someone help me with optimizing this program?

Limitations:

time: 4 seconds
memory: 512 mb

Code:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    private static int[] a;
    public static void swap(int i){
        int temp=a[i];
        a[i]=a[i-1];
        a[i-1]=temp;
    }
    public static void rotate(int times,int n){
        for(int j=0;j<times;j++)
            for(int i=n-1;i>0;i--)
              swap(i);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int q = in.nextInt();
        a = new int[n];
        int m[]=new int[q];
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
        }
        for(int a0 = 0; a0 < q; a0++){
            m[a0] = in.nextInt();
        }

        rotate(k%n,n);

        for(int a0 = 0; a0 < q; a0++){
           System.out.println(a[m[a0]]);
        }

    }
}

I think there must be some better way to swap or rotate the array.

your rotate thing executes the swap method 7,282,300,000 times - so yes it's going to take some time... Rotating your array n times should be equivalent to moving all elements by n%length once, no? That would be *much* quicker. — assylias, Dec 29 '16 at 16:52

score 0 · Answer 1 · answered Dec 29 '16 at 16:59

I don't think that there is need to actually rotate the array... You can just print the position which is the expected position after rotation is performed.

   //rotate(k%n,n);

    for(int a0 = 0; a0 < q; a0++){
       if(m[a0]+(k%n)>n)
         System.out.println((a[m[a0]+(k%n)-n]));
       else
         System.out.println((a[m[a0]+(k%n)]))
    }

score 0 · Answer 2 · edited May 23 '17 at 11:53

Use reversal rotate algotithm to achieve linear complexity.

import java.util.*;

class Solution {
    private static int[] a;

    private static void reverse(int l, int r) {
        r--;
        while (l < r) {
            int tmp = a[l];
            a[l] = a[r];
            a[r] = tmp;
            l++;
            r--;
        }
    }

    private static void rotate(int k, int n) {
        reverse(0, n - k);
        reverse(n - k, n);
        reverse(0, n);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int q = in.nextInt();
        a = new int[n];
        int m[] = new int[q];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        for (int i = 0; i < q; i++) {
            m[i] = in.nextInt();
        }

        rotate(k % n, n);

        for (int i = 0; i < q; i++) {
            System.out.println(a[m[i]]);
        }
    }
}

score 0 · Answer 3 · answered Sep 16 '20 at 06:04

To Rotate Array in right direction

public static int[] solve(int m[],int k){
    for(int i=0;i<k;i++){
        int last=m[m.length-1];
        for(int j=m.length-1;j>0;j--){
            m[j]=m[j-1];
        }
        m[0]=last;
    }
    return m;
}

***input:- m[]={1,2,3,4,5}; k=2;

output:- 4 5 1 2 3***

Optimize program for array rotation

3 Answers3