How can we rotate the array to the left?
EX: I have an array {1, 2, 3, 4, 5}
and an integer 7
It will rotate spaces 7
to the right, for example:{4, 5, 1, 2, 3}
I also have an array {1, 2, 3, 4, 5}
and an integer -7
It will rotate the spaces to the 7
left like:{3, 4, 5, 1, 2}
I have rotated the array to the right using:
for(int i = 0; i < data.length; i++){
result[(i+n) % data.length ] = data[i];
}
But how can we rotate the array to the left?
source to share
A left rotation n is the same as a right rotation along the length -n.
Turn right (for positive n):
for(int i = 0; i < data.length; i++){
result[(i+n) % data.length ] = data[i];
}
Turn left (for positive n):
for(int i = 0; i < data.length; i++){
result[(i+(data.length-n)) % data.length ] = data[i];
}
This way you can avoid modulo a negative number.
If you want to enter an integer n that rotates to the right if n is positive and to the left if n is negative, you can do it like this:
int[] rotateArray(int n, int[] data)
{
if(n < 0) // rotating left?
{
n = -n % data.length; // convert to +ve number specifying how
// many positions left to rotate & mod
n = data.length - n; // rotate left by n = rotate right by length - n
}
int[] result = new int[data.length];
for(int i = 0; i < data.length; i++){
result[(i+n) % data.length ] = data[i];
}
return result;
}
source to share
In the case of turning left, you can use this to avoid modulating a negative number:
int[] data = {1, 2, 3, 4, 5};
int[] result = new int[data.length];
for (int i = 0; i < data.length; i++) {
result[(i + (data.length - 2)) % data.length] = data[i];
}
for (int i : result) {
System.out.println(i);
}
source to share
You can also use linked list to achieve the same.
Integer[] arr = {1,2,3,4,5};
LinkedList<Integer> ns = new LinkedList<Integer>(Arrays.asList(arr));
int rotate=3;
if(rotate<0)
rotate += arr.length;
List<Integer> leftlist = ns.subList(0, rotate);
List<Integer> rightlist = ns.subList(rotate, arr.length);
LinkedList<Integer> result = new LinkedList<Integer>();
result.addAll(rightlist);
result.addAll(leftlist);
System.out.println(result);
source to share
If you want to rotate an array named a[n]
where n
is the size of the array and d
is the rotation number (in your case d=7
), you can use this code:
d = d % n;
for(int i=d;i<n;i++){
System.out.print(a[i]+" ");
}
for(int i=0;i<(d);i++){
System.out.print(a[i]+" ");
}
This code will print the elements of the array in order after performing a left rotation. If you want, you can store it in another array, or show the elements of the array as shown in the above method.
source to share
Here is a complete java program for n left rotations of an array.
public class ArrayRotation {
private static Scanner sc;
public static void main(String[] args) {
int n,k;
sc = new Scanner(System.in);
System.out.print("Enter the size of array: ");
n = sc.nextInt();
int[] a = new int[n];
System.out.print("Enter the "+n+" elements in the list: ");
for(int i=0;i<n;i++)
a[i] = sc.nextInt();
System.out.print("Enter the number of left shifts to array: ");
k = sc.nextInt();
System.out.print("Array before "+k+" shifts: ");
display(a);
solution(a,k);
System.out.println();
System.out.print("Array after "+k+" shifts: ");
display(a);
}
public static void solution(int[] a, int k){
int temp=0, j;
for(int i=0;i<k;i++){
temp = a[0];
// j=0; // both codes work i.e. for loop and while loop as well
// while(j<a.length-1){
// a[j]=a[j+1];
// j++;
// }
for(j=0;j<a.length-1;j++)
a[j]=a[j+1];
a[j]=temp;
}
}
public static void display(int[] a){
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
}
}
source to share
public static int[] arrayLeftRotation(int[] array, int elements, int rotations) {
// i = checks number of rotations
for (int i = 0; i < rotations; i++) {
int first = array[0];
int last = array[elements - 1];
// j = rotates each element
for (int j = 0; j < elements; j++) {
// check if at first index
if (j == 0) {
array[elements - 1] = first;
}
// check if at last index
if (j == (elements - 1)) {
// if at last index: make element in index before last = to last element
array[elements - 2] = last;
} else {
array[j] = array[j + 1];
}
}
}
return array;
}
source to share
This is the cleanest answer I could think of. Note that you need to compute a number rotations % length
to make your program work with more turns than the size of your array.
static int[] rotateLeft(int[] arr, int rotations) {
int length = arr.length;
int[] result = new int[length];
rotations = rotations % length; // robust to rotations > length
int position = length - rotations; // compute outside the loop to increase performance
for (int i = 0; i < length; i++) {
result[(position + i) % length] = arr[i];
}
return result;
}
source to share
I used the approach below, putting the array into a new array at a new position.
int length = a.length;
int[] newArr = new int[a.length];
for (int i = length - 1; i >= 0 ; i--){
int newPosition = i - d; // d is the number of rotation
if (newPosition < 0)
newPosition = length + newPosition;
newArr[newPosition] = a[i];
}
I originally wanted to swap in the same array using the approach below, but it didn't work in all cases. For example, when 2 elements of an array are swapped due to rotation. Thus, newPosition and position continue to point to each other. Consequently, the rest of the array is not moved. Not sure if it is possible to rotate an array with O (n) complexity in the same array.
int length = a.length;
int position = length-1;
int temp = a[position];
for (int i = 0; i < length; i++){
int newPosition = position - d;
if (newPosition < 0)
newPosition = length + newPosition;
int cache = a[newPosition];
a[newPosition]= temp;
temp = cache;
position = newPosition;
}
source to share
Here is my solution in Javascript: n is the number of elements and r is the number of rotations. and this is an array.
function rotate(a,r,n)}
for(var i = 0; i<r; i++){
var aa = array[0] //
for (var j = 0; j < n-1; j++){
array[j] = array[j+1] //
}
array[n-1] = aa //
}
return a
}
var array = [1,2,3,4,5];
console.log(rotate(array,1,5))
source to share