Showing posts with label Array rotate. Show all posts
Showing posts with label Array rotate. Show all posts

Rotate array by N elements

Given an array, cyclically rotate the array clockwise by N elements. The conditions are 

  • Should NOT use temporary array to store values
  • N should be > 0 and <= given array size
Sample:

Array Rotate

We will see how to rotate the array by two ways.

  • 1st lets see simple solution that takes 1st element and swap with last element for N times and each time array values will be moved 1 position front like arr[i] = arr[i+1]
  • 2nd lets see swapping 0th to xth all elements, next swapping all from xth to last element and finally swapping all elements from 0th to last element with 3 for loops independently. 


METHOD-1:

public class ArrayRotate {

 public static void main(String[] args) {

  int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

  printArray("BEFORE ROTATE :::: ", array);

  rotate(array, 5);

  printArray("AFTER ROTATE ::::: ", array);

 }

 private static void printArray(String txt, int array[]) {
  System.out.print(txt + " ::: ");
  for (int i : array) {
   System.out.print(i + ", ");
  }
  System.out.println();
 }

 private static void rotate(int[] array, int startLoc) {

  if (startLoc < 0 || startLoc > array.length) {
   System.out.println("Out of array index !!!");
   return;
  }

  for (int i = 0; i < startLoc - 1; i++) {
   int tmp = array[0];
   for (int j = 0; j < array.length - 1; j++) {
    array[j] = array[j + 1];
   }
   array[array.length - 1] = tmp;
  }
 }
}

OUTPUT:

BEFORE ROTATE ::::  ::: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
AFTER ROTATE :::::  ::: 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 



METHOD-2:


public class RotateArray {

 public static void main(String[] args) {

  int array[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };

  printArray("BEFORE ROTATE :::: ", array);

  rotate(array, 5);

  printArray("AFTER ROTATE ::::: ", array);

 }

 private static void printArray(String txt, int array[]) {
  System.out.print(txt + " ::: ");
  for (int i : array) {
   System.out.print(i + ", ");
  }
  System.out.println();
 }

 private static void rotate(int[] array, int startLoc) {
  
  if (startLoc < 0 || startLoc > array.length) {
      System.out.println("Out of array index !!!");
      return;
  }
  
  for(int i=0,j=startLoc-2;i<j;i++,j--) {
   int tmp = array[i];
   array[i] = array[j];
   array[j] = tmp;
  }
  
  for(int i=startLoc-1,j=array.length-1;i<j;i++,j--) {
   int tmp = array[i];
   array[i] = array[j];
   array[j] = tmp;
  }

  for(int i=0,j=array.length-1;i<j;i++,j--) {
   int tmp = array[i];
   array[i] = array[j];
   array[j] = tmp;
  }
 }
}


OUTPUT:


BEFORE ROTATE ::::  ::: 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 
AFTER ROTATE :::::  ::: 15, 16, 17, 18, 19, 20, 11, 12, 13, 14,