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