Array Rotation - Three Solutions

Array rotation by k places can be done by using extra space of k sized array, by shifting array by one position in loop of k, by shifting array by gcd(array.length, k) in gcd number of sets. Following program has all the implementations:

	package arrays;
	public class ArrayRotation {
	public static void rotateByOne(int[] a) {
	int n = a.length, tmp=a[0];
	for(int i=0;i<n-1;i++) {
	a[i]=a[i+1];
	}
	a[n-1]=tmp;
	print(a);
	}
	public static void rotateByX(int[] a, int init, int x) {
	int n = a.length, tmp=a[init];
	int d =n-x+init;
	for(int i=init;i<d;i=i+x) {
	a[i]=a[i+x];
	}
	a[d]=tmp;
	print(a);
	}
	public static void rotateNoExtraSpace(int[] a,int k) {
	for(int i=0;i<k;i++) {
	rotateByOne(a);
	}
	}
	public static int gcd2(int a,int b) {
	if(a==0)
	return b;
	return gcd2(b%a,a);
	}
	public static void rotateJuggle(int[] a,int k) {
	int n = a.length;
	int g = gcd2(n,k);
	for(int i=0;i<g;i++) {
	rotateByX(a,i,g);
	}
	}
	public static void rotateExtraSpace(int[] a,int k) {
	int n = a.length;
	print(a);
	int[] tmp = new int[k];
	for(int i=0;i<k;i++) {
	tmp[i]=a[i];
	}
	for(int i=0;i<n-k;i++) {
	a[i]=a[i+k];
	}
	int j=0;
	for(int i=n-k;i<n;i++) {
	a[i]=tmp[j++];
	}
	print(a);
	}
	public static void print(int[] a) {
	System.out.println();
	for(int i:a)
	System.out.print("---"+i);
	}
	public static void main(String[] args) {
	int[] a1= {1,2,3,4,5};
	rotateExtraSpace(a1,2);//3,4,5,1,2
	rotateNoExtraSpace(a1,2);
	int[] a2={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
	rotateJuggle(a2,3);
	}
	}

view raw ArrayRotation.java hosted with ❤ by GitHub