Circular Array Rotation
Right circular rotation on an array of integers [1,2,...,n-1,n]. After performing one right circular rotation operation, the array is transformed from [1,2,...,n-1,n] to [n,1,2,...,n-1].
Perform rotation k number of times and find out element in particular position.
Inputs :
Line One : Size of array, Number of rotation, Number of positions going to print.
Line Two : Array of integers.
Next lines will be positions to find after rotations.
Sample :
Inputs :
3 2 3
1 2 3
0
1
2Output :
2
3
1
Here Array is [1 2 3], We are going to rotate it two times.
Rotation One : [3 1 2]
Rotation Two : [2 3 1]
Now Positions
0 is 2
1 is 3
2 is 1
Algorithm :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
package com.omt.learn.algo; import java.util.Scanner; public class CircularArrayRotation { public static void main(String[] args) { Scanner sn = new Scanner(System.in); String[] lineOne = sn.nextLine().split("\\s+"); String[] lineTwo = sn.nextLine().split("\\s+"); int size = Integer.parseInt(lineOne[0]); int rotate = Integer.parseInt(lineOne[1]); int querySize = Integer.parseInt(lineOne[2]); int[] qInt = new int[querySize]; for (int i = 0; i < querySize; i++) { qInt[i] = Integer.parseInt(sn.nextLine()); } for (int position : qInt) { //System.out.println("Poositions:" + position); System.out.println(find(lineTwo, rotate, position, size)); } } public static int find(String a[], int rotation, int position, int size) { int index = size - rotation + position; return getElement(a, index, size); } public static int getElement(String a[], int index, int size) { if (index == size) { return Integer.parseInt(a[0]); } else if (index > size) { int div = Math.abs(index) / size; index -= (div * size); return getElement(a, index, size); } else if (index < 0) { if (Math.abs(index) > size) { int div = Math.abs(index) / size; index += (div * size); } else { index += size; } return getElement(a, index, size); } else { return Integer.parseInt(a[index]); } } } |
