Commit a3536b9

committed

added array rotation 3 approaches

1 parent e64c51f commit a3536b9Copy full SHA for a3536b9

File tree

+171

-68

lines changed

+171

-68

lines changed

Lines changed: 42 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,42 @@`
	`1`	`+/*`
	`2`	`+ * ARRAY ROTATION USING TEMP ARRAY`
	`3`	`+ * LEFT ROTATE TO 2`
	`4`	`+ */`
	`5`	`+import java.util.*;`
	`6`	`+public class ArrayRotation1`
	`7`	`+{`
	`8`	`+ public static void main(String[] args)`
	`9`	`+ {`
	`10`	`+ Scanner in = new Scanner(System.in);`
	`11`	`+ int[] arr = {1,2,3,4,5,6,7};`
	`12`	`+ int shift=2;`
	`13`	`+`
	`14`	`+ rotate(arr,shift,arr.length);`
	`15`	`+`
	`16`	`+ in.close();`
	`17`	`+ }`
	`18`	`+ public static void rotate(int[] arr,int d,int n)`
	`19`	`+ {`
	`20`	`+ int[] temp = new int[d];`
	`21`	`+ //copy arr 2 elements to temp`
	`22`	`+ for(int i=0;i<temp.length;i++)`
	`23`	`+ {`
	`24`	`+ temp[i] = arr[i];`
	`25`	`+ }`
	`26`	`+ //shifting array`
	`27`	`+ for(int i=0;i<arr.length-d;i++)`
	`28`	`+ {`
	`29`	`+ arr[i]=arr[i+d];`
	`30`	`+ }`
	`31`	`+ //copy temp array to array`
	`32`	`+ for(int i=0;i<d;i++)`
	`33`	`+ {`
	`34`	`+ arr[i+arr.length-d] =temp[i];`
	`35`	`+ }`
	`36`	`+ for(int i=0;i<arr.length;i++)`
	`37`	`+ {`
	`38`	`+ System.out.print(arr[i]+" ");`
	`39`	`+ }`
	`40`	`+ System.out.println();`
	`41`	`+ }`
	`42`	`+}`

Lines changed: 35 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,35 @@`
	`1`	`+/*`
	`2`	`+ * ARRAY ROTATION USING ONE ELEMENT`
	`3`	`+ * LEFT ROTATE BY 2`
	`4`	`+ */`
	`5`	`+import java.util.*;`
	`6`	`+public class ArrayRotation2`
	`7`	`+{`
	`8`	`+ public static void main(String[] args)`
	`9`	`+ {`
	`10`	`+ Scanner in = new Scanner(System.in);`
	`11`	`+ int[] arr={1,2,3,4,5,6,7};`
	`12`	`+ int shift=3;`
	`13`	`+ rotate(arr, shift, arr.length);`
	`14`	`+`
	`15`	`+ //printing array`
	`16`	`+ for(int i=0;i<arr.length;i++)`
	`17`	`+ {`
	`18`	`+ System.out.print(arr[i]+" ");`
	`19`	`+ }`
	`20`	`+ in.close();`
	`21`	`+ }`
	`22`	`+ public static void rotate(int[] arr,int d,int n)`
	`23`	`+ {`
	`24`	`+ //we can shift one by one`
	`25`	`+ for(int i=0;i<d;i++)`
	`26`	`+ {`
	`27`	`+ int temp = arr[0];`
	`28`	`+ for(int j=0;j<n-1;j++)`
	`29`	`+ {`
	`30`	`+ arr[j]=arr[j+1];`
	`31`	`+ }`
	`32`	`+ arr[n-1]=temp;`
	`33`	`+ }`
	`34`	`+ }`
	`35`	`+}`

Lines changed: 44 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,44 @@`
	`1`	`+abstract class jugglingAlgo`
	`2`	`+{`
	`3`	`+ public static void main(String[] args)`
	`4`	`+ {`
	`5`	`+ int[] arr = {1,2,3,4,5,6,7,8,9};`
	`6`	`+ leftRotation(arr,3);`
	`7`	`+ for(int i=0;i<arr.length;i++)`
	`8`	`+ {`
	`9`	`+ System.out.print(arr[i] + " ");`
	`10`	`+ }`
	`11`	`+ System.out.println();`
	`12`	`+ }`
	`13`	`+ public static int[] leftRotation(int[] arr,int k)`
	`14`	`+ {`
	`15`	`+ int set = gcd(arr.length, k);`
	`16`	`+`
	`17`	`+ for(int i=0;i<set;i++)`
	`18`	`+ {`
	`19`	`+ int temp = arr[i];`
	`20`	`+ int j=i;`
	`21`	`+ while(true)`
	`22`	`+ {`
	`23`	`+ int d = (j+k) % arr.length;`
	`24`	`+`
	`25`	`+ if(d==i)`
	`26`	`+ {`
	`27`	`+ break;`
	`28`	`+ }`
	`29`	`+ arr[j] = arr[d];`
	`30`	`+ j=d;`
	`31`	`+ }`
	`32`	`+ arr[j] = temp;`
	`33`	`+ }`
	`34`	`+ return arr;`
	`35`	`+ }`
	`36`	`+ public static int gcd(int a,int b)`
	`37`	`+ {`
	`38`	`+ if(b==0)`
	`39`	`+ {`
	`40`	`+ return a;`
	`41`	`+ }`
	`42`	`+ return gcd(b,a%b);`
	`43`	`+ }`
	`44`	`+}`

Lines changed: 4 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -17,6 +17,10 @@`
`17`	`17`	`* MISC`
`18`	`18`	`* JAGGED ARRAY`
`19`	`19`	`* [SPIRAL ORDER MATRIX](Data-Structures/ARRAYS/MISC/spiralOrder.java)`
	`20`	`+ * Rotate 1D array to left by K`
	`21`	`+ * APPROACH 1: [rotate array using temp array](Data-Structures/ARRAYS/MISC/ArrayRotation1.java)`
	`22`	`+ * APPROACH 2: [rotate array by rotating one element](Data-Structures/ARRAYS/MISC/ArrayRotation2.java)`
	`23`	`+ * APPROACH 3: [rotate array using Juggling Algorithm](Data-Structures/ARRAYS/MISC/jugglingAlgo.java)`
`20`	`24`
`21`	`25`	`#### STRING`
`22`	`26`

Comments

(0)