Given an array of integers, there we cyclically permute its elements, that is, shift each array element to the left by one index. The first value will go into the last index.
Example:
Input: [1,2,3,4,5] Output: [2,3,4,5,1] Input: [2,3,1,5,6] Output: [3,1,5,6,2]
Approach #1
- In function cyclicShift(), the loop for(i=0; i<arr.length; i++) traverses through the array and shifts each element one position before.
- The first value of the array is stored in variable x before the loop.
- Finally, the last element of the array is set to x.
Java
// Java Program to Cyclically Permute// the Elements of an Arrayimport java.util.*;import java.io.*;// function to print the arrayclass cycle { public int[] cycleShift(int[] arr) { int x = arr[0]; // store a[0] int i; for (i = 0; i < arr.length - 1; i++) { // for other element shift left arr[i] = arr[i + 1]; } // for the last element in the modified array // it will be starting element arr[i] = x; return arr; }}public class GFG { public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5 }; cycle c = new cycle(); int[] newArray = c.cycleShift(arr); for (int i = 0; i < newArray.length; i++) { System.out.print(newArray[i] + " "); } }} |
Output
2 3 4 5 1
- Time Complexity: O(n), where n is the number of elements in the array.
- Space Complexity: O(1)
Approach #2: Using Swapping
In the function cyclicSwap(arr) the loop for(int i = 0; i < arr.length; i++) the swap the first element to its next element in the array
- In First Iteration after swapping it will be, original array [1, 2, 3, 4, 5] –> [2, 1, 3, 4, 5];
- In the second Iteration again after swapping [2, 1, 3, 4, 5] –> [2, 3, 1, 4, 5];
- And this iteration is going on till the loop end Final result would be like this [2, 3, 4, 5, 1]
Below is the implementation of the above approach.
Java
// Java Program to Cyclically Permute// the Elements of an Arrayimport java.io.*;import java.util.*;class GFG { public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5 }; int first = arr[0]; int start = 0; // swapping each element with the first // element for (int i = 1; i < arr.length; i++) { arr[start++] = arr[i]; arr[i] = first; } // Printing the element in the // array....... for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } }} |
Output
2 3 4 5 1
- Time Complexity: O(n)
- Space Complexity: O(1)
Approach #3: using the Queue to make the cyclic permute in the array
First, insert all the elements into the queue of from index 1 to arr.length;
dequeue the queue and store back to the array and at last, put the first element to the last index of the array
Java
// Java Program to Cyclically Permute// the Elements of an Arrayimport java.io.*;import java.util.*;class GFG { public static void main(String[] args) { // use of the queue to do // cyclic shift in the array int[] arr = { 1, 2, 3, 4, 5 }; Queue<Integer> q = new LinkedList<>(); int first = arr[0]; int strt = 0; // adding each element into the queue for (int i = 1; i < arr.length; i++) { q.add(arr[i]); } while (!q.isEmpty()) { arr[strt++] = q.poll(); } // Polling out the element from the // Queue and inserting into the queue arr[arr.length - 1] = first; for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } }} |
Output
2 3 4 5 1
- Time Complexity: O(n)
- Space Complexity: O(n)
