×

# ROTATION - Editorial

 1 Problem link : Contest Practice Difficulty : CakeWalk Pre-requisites : basic language data structures Solution: At first, let's note that if we rotate the array by K units anticlockwise, it's the same as the rotation by N-K units clockwise. So, from now on, we will consider only clockwise rotations. In case we have any anticlockwise rotation query, it can be reduced to the clockwise one. When we rotate the array by K units anticlockwise, its' first element becomes equal to the K mod N+1-th element of the initial array. The second element of this rotated array will be equal to (K+1) mod N+1-th element of the initial array, the third will be equal to the (K+2) mod N+1-th one, and so on (of course, we use 1-indexation in our considerations). So, using this facts one can simply get the M-th element of the array after a rotation. What happens when we have several rotations? One can note that the rotations are "additive", so we only need to maintain is the current "shift" variable that points to the first element of the current array after all the rotations. If this "shift" variable equals to R before some clockwise turn, it will be equal to (R+K) mod N after this turn. Basically, like it is described in the previous paragraph, we can get the M-th element of the current array as A[(R+M-1) mod N], where A is the array that was given initially. In this solution we don't actually rotate the array, we only operate with out "shift" variable (R above). So each operation is performed in O(1) time, so we get the total complexity of O(N+Q) where N is the size of the array and Q is the number of queries. Setter's solution: link Tester's solution: link This question is marked "community wiki". asked 15 Sep '14, 15:44 719●43●63●77 accept rate: 0% 1.3k●15●65●81

 0 where I'm getting Wrong in this answer :\ #include int main() { int n,m,i,start=1,inp,index; char ch[1]; static int a[100001]; scanf("%d %d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=m;i++) { scanf("%s %d",&ch,&inp); if(ch[0]=='C') { start=(start+inp); if(start>n) start-=n; } else if(ch[0]=='A') { start=(start-inp); if(start<1) start+=n; } else { index=start+inp-1; if(index>n) index-=n; if(index<1) index+=n; printf("%d\n",a[index]); } } return 0; } answered 15 Sep '14, 21:14 25●2●6●9 accept rate: 0% if(index>n) index-=n; But what if index=11 and n=5, then index=11-5=6, which is still greater. So instead use % operator, index=11%5=1,the correct ans. Hope this will help. (07 Oct '14, 09:43) mskanyal2★ You should use indexing with 0, since there are some mod(%) operation and index%n=0, if index==n. (07 Oct '14, 10:16) mskanyal2★

WOW! Got to know an interesting fact while looking for this problem!

## and in c/c++: -32%5 = -2

202
accept rate: 0%

 -1 import java.io.BufferedReader; import java.io.InputStreamReader; class ROTATION { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String input[] = in.readLine().split(" "); int n = Integer.parseInt(input[0],10); int m = Integer.parseInt(input[1],10); int arr[] = new int[n]; input = in.readLine().split(" "); for(int i = 0;i0) { input = in.readLine().split(" "); char c[] = input[0].toCharArray(); char a = c[0]; if(a=='C') { index = index + Integer.parseInt(input[1],10) ; if(index>=n) index = index -n; } else if(a=='A') { index = index - Integer.parseInt(input[1],10) ; if(index<0) index = index + n; } else if(a=='R') { tempIndex = index; tempIndex = tempIndex + Integer.parseInt(input[1],10) -1; if(tempIndex>=n) tempIndex = tempIndex-n; if(tempIndex<0) tempIndex = tempIndex + n; System.out.println(arr[tempIndex]); } } }  } answered 15 Sep '14, 17:20 0 accept rate: 0% if(tempIndex>=n) tempIndex = tempIndex-n; what is tempindex=11, and n=5, tempIndex=11-5=6, which is not a valid array index in this situation... Hope this will help, and happy coding. (07 Oct '14, 09:48) mskanyal2★

Hi ,

Could you let me know what is wrong.

My code is shown below

# include <iostream>

using namespace std; int main() { int M, N; int A[100001]; int B[100001]; char operation; int unit; scanf("%d %d",&N, &M); int j; for ( int i = 1; i<= N; i++) { scanf("%d", &A[i]); B[i] = A[i]; } for ( int k = 0; k<M; k++) { fflush(stdin); scanf("%c %d",&operation, &unit); if ( operation == 'R') { printf("%d\n",A[unit]); } else if ( operation == 'C') { j = 1; //A[0] = A[unit]; for ( int i = unit+1; i<=N; i++) { A[j] = B[i]; j++; } for ( int i = 1; i<=unit; i++) { A[j] = B[i]; j++; } for ( int i =1;i<=N;i++) { B[i] = A[i]; printf("%d ",B[i]); } printf("\n");

        }
else if ( operation == 'A')
{
j = 1;
for ( int i =1;i<unit;i++)
{
A[(N-(unit-i))+1] = B[i];
}
for ( int i=unit;i<=N;i++)
{
A[j] = B[i];
j++;
}
for ( int i =1;i<=N;i++)
{
B[i] = A[i];
printf("%d ",B[i]);
}
printf("\n");

}
}
return 0;


}

2★k1ps
-2
accept rate: 0%

2

(03 Jun '15, 10:22)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,639
×1,646
×935
×61

question asked: 15 Sep '14, 15:44

question was seen: 4,947 times

last updated: 29 Oct '17, 02:47