Tuesday 28 July 2015

Rotate elements in an array (anti clock wise)

Rotate elements in an array clockwise.

Suppose array has elements {1, 2, 3, 4, 5}.

After 1st rotation, elements like {2, 3, 4, 5, 1}.
After 2nd rotation, elements like {3, 4, 5, 1, 2}
After 3rd iteration, elements like {4, 5, 1, 2, 3}
After 4th iteration, element like {5, 1, 2, 3, 4}
After 5th iteration, elements like {1, 2, 3, 4, 5}

As you observe above sequence, at 5th iteration, array comes to its original position.

Approach1
Approach1 is simple. Suppose you want to rotate elements 2 times, create a temporary array of size 2, and copy first 2 elements of original array to temporary array. Move remaining the elements of original array to front. Copy elements of temporary array to the end of actual array.

Step 1: Suppose I had array with elements {1, 2, 3, 4, 5}. I want to rotate 2 times.
Step 2: Create temporary array of size 2 and copy first 2 elements of array to this temporary array.
Step 3: Move 5-2 = 3 elements of array to front.
Step 4: Copy elements of temporary array to the end of original array.

Find complete working application below.
import java.util.Objects;

public class RotateArray {
 public static void rotate(int arr[], int noOfTimes) {
  Objects.nonNull(arr);
  if (noOfTimes < 0)
   throw new IllegalArgumentException("Rotation should be positive");

  int length = arr.length;

  if (length == 1)
   return;

  if (noOfTimes > length)
   noOfTimes = noOfTimes % length;

  if (noOfTimes == 0)
   return;

  int temp[] = new int[noOfTimes];

  for (int i = 0; i < noOfTimes; i++) {
   temp[i] = arr[i];
  }

  int count1 = 0;
  for (int j = noOfTimes; j < length; j++) {
   arr[count1++] = arr[j];
  }

  int count2 = 0;
  for (int k = count1; k < length; k++) {
   arr[k] = temp[count2++];
  }

 }
}

Approach2
Approach 2 is somewhat tricky. Suppose array arr has ‘n’ elements and you have to rotate array k (1 < k < n) times. Following is the step-by-step procedure.

Suppose array has n=5 elements and rotate 2 (k=2) times.
Step 1: Reverse first k elements of array. If k =2 and n=5.
Step 2: Reverse k+1 to n elements of array.
Step 3: Reverse total elements of array.

import java.util.Objects;

public class RotateArrayApproach2 {
 private static void reverseArray(int arr[], int start, int noOfElements) {
  Objects.nonNull(arr);
  if (arr.length == 1 || noOfElements > arr.length || noOfElements < 2)
   return;

  int end = noOfElements - 1;
  int temp;

  while (start < end) {
   temp = arr[start];
   arr[start] = arr[end];
   arr[end] = temp;
   start++;
   end--;
  }
 }

 public static void rotate(int arr[], int noOfTimes) {
  Objects.nonNull(arr);
  if (noOfTimes < 0)
   throw new IllegalArgumentException("Rotation should be positive");

  int length = arr.length;

  if (length == 1)
   return;

  if (noOfTimes > length)
   noOfTimes = noOfTimes % length;

  if (noOfTimes == 0)
   return;

  reverseArray(arr, 0, noOfTimes);
  reverseArray(arr, noOfTimes, arr.length);
  reverseArray(arr, 0, arr.length);
 }
}


Following is the junit test case for above applications.

import static org.junit.Assert.assertArrayEquals;

import org.junit.Test;

public class RotateArrayTest {
 @Test
 public void testNormal_1() {
  int actual1[] = { 1, 2, 3, 4, 5 };
  int actual2[] = { 1, 2, 3, 4, 5 };
  int actual3[] = { 1, 2, 3, 4, 5 };
  int actual4[] = { 1, 2, 3, 4, 5 };
  int actual5[] = { 1, 2, 3, 4, 5 };
  int actual6[] = { 1, 2, 3, 4, 5 };
  int actual7[] = { 1, 2, 3, 4, 5 };
  int actual8[] = { 1, 2, 3, 4, 5 };
  int actual9[] = { 1, 2, 3, 4, 5, 6, 7 };

  int expected1[] = { 2, 3, 4, 5, 1 };
  int expected2[] = { 3, 4, 5, 1, 2 };
  int expected3[] = { 4, 5, 1, 2, 3 };
  int expected4[] = { 5, 1, 2, 3, 4 };
  int expected5[] = { 1, 2, 3, 4, 5 };
  int expected9[] = { 3, 4, 5, 6, 7, 1, 2 };

  RotateArray.rotate(actual1, 1);
  RotateArray.rotate(actual2, 2);
  RotateArray.rotate(actual3, 3);
  RotateArray.rotate(actual4, 4);
  RotateArray.rotate(actual5, 5);
  RotateArray.rotate(actual6, 6);
  RotateArray.rotate(actual7, 7);
  RotateArray.rotate(actual8, 8);
  RotateArray.rotate(actual9, 2);

  assertArrayEquals(expected1, actual1);
  assertArrayEquals(expected2, actual2);
  assertArrayEquals(expected3, actual3);
  assertArrayEquals(expected4, actual4);
  assertArrayEquals(expected5, actual5);
  assertArrayEquals(expected1, actual6);
  assertArrayEquals(expected2, actual7);
  assertArrayEquals(expected3, actual8);
  assertArrayEquals(expected9, actual9);
 }

 @Test(expected = NullPointerException.class)
 public void testNULLCondition_1() {
  RotateArray.rotate(null, 3);
 }

 @Test(expected = IllegalArgumentException.class)
 public void testIllegalArgument() {
  RotateArray.rotate(new int[] {}, -1);
 }

 @Test
 public void testNormal_2() {
  int actual1[] = { 1, 2, 3, 4, 5 };
  int actual2[] = { 1, 2, 3, 4, 5 };
  int actual3[] = { 1, 2, 3, 4, 5 };
  int actual4[] = { 1, 2, 3, 4, 5 };
  int actual5[] = { 1, 2, 3, 4, 5 };
  int actual6[] = { 1, 2, 3, 4, 5 };
  int actual7[] = { 1, 2, 3, 4, 5 };
  int actual8[] = { 1, 2, 3, 4, 5 };
  int actual9[] = { 1, 2, 3, 4, 5, 6, 7 };

  int expected1[] = { 2, 3, 4, 5, 1 };
  int expected2[] = { 3, 4, 5, 1, 2 };
  int expected3[] = { 4, 5, 1, 2, 3 };
  int expected4[] = { 5, 1, 2, 3, 4 };
  int expected5[] = { 1, 2, 3, 4, 5 };
  int expected9[] = { 3, 4, 5, 6, 7, 1, 2 };

  RotateArrayApproach2.rotate(actual1, 1);
  RotateArrayApproach2.rotate(actual2, 2);
  RotateArrayApproach2.rotate(actual3, 3);
  RotateArrayApproach2.rotate(actual4, 4);
  RotateArrayApproach2.rotate(actual5, 5);
  RotateArrayApproach2.rotate(actual6, 6);
  RotateArrayApproach2.rotate(actual7, 7);
  RotateArrayApproach2.rotate(actual8, 8);
  RotateArrayApproach2.rotate(actual9, 2);

  assertArrayEquals(expected1, actual1);
  assertArrayEquals(expected2, actual2);
  assertArrayEquals(expected3, actual3);
  assertArrayEquals(expected4, actual4);
  assertArrayEquals(expected5, actual5);
  assertArrayEquals(expected1, actual6);
  assertArrayEquals(expected2, actual7);
  assertArrayEquals(expected3, actual8);
  assertArrayEquals(expected9, actual9);
 }

 @Test(expected = NullPointerException.class)
 public void testNULLCondition_2() {
  RotateArrayApproach2.rotate(null, 3);
 }

 @Test(expected = IllegalArgumentException.class)
 public void testIllegalArgument_2() {
  RotateArrayApproach2.rotate(new int[] {}, -1);
 }

}

No comments:

Post a Comment