"Fun with Rotation" - Codechef September Challenge

Question

Can you please help me in reducing the complexity of the below code? The problem statement can be found here.

You are given an array A of N integers. You are to fulfill M queries. Each query has one of the following three types:

C d : Rotate the array A clockwise by d units.
A d : Rotate the array A anticlockwise by d units.
R d : Query for the value of the element, currently being the d-th in the array A.

Input

The first line contains two numbers - N and M respectively. The next line contains N space separated Integers, denoting the array A. Each of the following M lines contains a query in the one of the forms described above.

Output

For each query of type R output the answer on a separate line.

Constraints

1 ≤ N ≤ 100000
1 ≤ M ≤ 100000
1 ≤ d ≤ N, in all the queries
1 ≤ elements of A ≤ 1000000

The array A and the queries of the type R are 1-based.

The solution in Java manages to solve the problem but is facing a time limit exceeded issue, so please advise me on how to optimize the code.

import java.io.BufferedReader;

 import java.io.IOException;

 import java.io.InputStreamReader;

 import java.util.ArrayList;





 public class Main {



    public static void main (String args[]) throws IOException


    {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));


        String not[]=in.readLine().trim().split(" ");


        int n=Integer.parseInt(not[0]);


        int q=Integer.parseInt(not[1]);


        String s[]=in.readLine().trim().split(" ");


    ArrayList<Integer>  sarray=new ArrayList<Integer>();



        for(int i=0;i<n;i++)

        {



        sarray.add(Integer.parseInt(s[i]));




        }


        for(int j=0;j<q;j++)

        {


            String r[]=in.readLine().trim().split(" ");




            if(!r[0].equals("R"))   
            sarray=swap(sarray,n,Integer.parseInt(r[1]),r[0]);

            else

                System.out.println(sarray.get(Integer.parseInt(r[1])-1));







            }


    }






    private static ArrayList<Integer> swap(ArrayList<Integer> arr, int n, int d,String c) {

        // TODO Auto-generated method stub


        int i, j;
        int temp;  

        for(j = 0; j < d; j++)

        {      

            //rotate right once      

            if(c.equals("A"))

            {

            temp = arr.get(n - 1);   

            for(i = n - 1; i > 0; i--)

            arr.set(i,arr.get(i-1));
            arr.set(0,temp);

            }
            else  if(c.equals("C"))
            {

                  temp = arr.get(0);  
                  for(i = 0; i < n-1; i++) 
                  arr.set(i,arr.get(i + 1)); 
                  arr.set(n - 1,temp); 


            }






        }


        return arr;
    }



 }

Answer 1

• Your outer class name should correspond to the type of program. There's no point in calling it Main since you already have to have a main() method. Of course, you'll have to be sure that your .java filename and outer class name are the same.

• You have a lot of excess whitespace, and I don't think it's a copy/paste error. Just get rid of all this whitespace so that it's easier for others to read.

  On the other hand, this could use more whitespace:

  for(int i=0;i<n;i++)
  

  It's good to separate each operator and operand so that the line is easier to read. Although keeping them together saves horizontal length, the line itself is already short, and even then there's little reason to cram everything together.

  for (int i = 0; i < n; i++)
  

• You're using single-character variable names such as n and s, and it's not at all clear what they mean in this code. If it were a tiny program, then it may be okay. But for this program, it's best to use meaningful names so that the code is self-documenting.

Answer 2

So much extra white space. As posted, you code is 138 lines. That is after I removed over ten blank lines (some of which had white space characters) after that last closing brace. Without making a single functional change to the code, I got it down to 60 lines.

---

You should properly indent your code. It will make things much easier to read.

---

That combined with the following makes things much worse.

Sometimes you use braces and sometimes you don't. Pick a style and be consistent. Always using them has some nice advantages.

temp = arr.get(0);
for(i = 0; i < n-1; i++)
arr.set(i,arr.get(i + 1));
arr.set(n - 1,temp);

is actually

temp = arr.get(0);
for(i = 0; i < n-1; i++) {
  arr.set(i,arr.get(i + 1));
}
arr.set(n - 1,temp);

But it is very hard to tell when everything is a straight line. But how do I know if you wanted the second arr.set() to be part of the loop? Maybe you added it later and assumed it would be part of the loop. Always including the braces will ensure that there is no confusion or accidental errors.

---

Variable names. Jamal already touched on single letter names.

not: This means nothing to me. Even looking at the code, I can't figure out why this string of characters was chosen.

sarray: The variable is not an array, it is a List. Event so, since Java is a strongly typed language, the code tells me it is a List. In post cases, the variable name does not need to indicate the object type.

Answer 3

Just store your elements in an array, and never move them around. You only need to provide the illusion of having shifted the array.

Representing the circular array using an object is probably a good idea.

public class CircularIntArray {
    private final int[] elements;
    private final int len;
    private int rotation;

    public CircularIntArray(int[] elements) {
        this.elements = elements;
        this.len = elements.length;
    }

    public void rotateClockwise(int offset) {
        this.rotation += offset;
        // Clamp rotation such that 0 <= rotation < len
        this.rotation %= len;
        if (this.rotation < 0) this.rotation += len;
    }

    public int get(int position) {
        // One-based indexing
        return this.elements[(position + rotation + len - 1) % len];
    }
}

Proof-of-concept based on the given example:

public static void main(String[] args) {
    CircularIntArray a = new CircularIntArray(new int[] {
        5, 4, 3, 3, 9
    });
    System.out.println(a.get(1));
    a.rotateClockwise(4);
    System.out.println(a.get(5));
    a.rotateClockwise(-3);
    System.out.println(a.get(2));
}