circular left shift of an array by n positions in java

Viewed 25978

I am trying to do the circular left shift of an array by n positions using only a single 1D array. I can do it in two arrays, but I haven't figured out how to do it using one. Please give your suggestions

15 Answers

Below I have implemented a sample solution to left shift or right shift the array by n element.

class RotateArrayByN {

    public void leftRotate(int arr[], int d, int n)
    {
        for (int i = 0; i < d; i++)
            leftRotatebyOne(arr, n);
    }

    public void rightRotate(int[] arr,int d, int n){
        for(int i=0;i<d;i++)
            rightRotatebyOne(arr,n);
    }

    public void leftRotatebyOne(int arr[], int n)
    {
        int i, temp;
        temp = arr[0];
        for (i = 0; i < n - 1; i++)
            arr[i] = arr[i + 1];
        arr[i] = temp;
    }

    public void rightRotatebyOne(int[] arr,int n){

        int temp=arr[n-1];
        for (int i=n-1;i>0;i--) {
            arr[i] = arr[i - 1];
        }
        arr[0]=temp;

    }

  public void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");

        System.out.println();
    }


    public static void main(String[] args)
    {
        RotateArrayByN rotate = new RotateArrayByN();
        int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
        System.out.println("Left Rotate");
        rotate.leftRotate(arr, 2, 7);
        rotate.printArray(arr, 7);

       //System.out.println("Right Rotate");
        //rotate.rightRotate(arr,2,7);
       // rotate.printArray(arr,7);
    }
} 

I have commented out the right shift.

I know it is an old post but I didn't see this posted anywhere so:

d is how many positions we want to shift to the left.

    int[] array = {1,2,3,4,5,6,7,8};
    int length = array.length;
    int d = 3;
    int[] ans = new int[length];        

    for (int i = 0; i < length; i++){
        ans[i] = array[(i + d)%length];
    }
    System.out.println(Arrays.toString(ans));

It will output: [4, 5, 6, 7, 8, 1, 2, 3]

You can see the code in action here: http://tpcg.io/8cS6GIKI

Edited: Nevermind...I cannot read. I just saw the OP is asking for only 1 Array. My bad. I will leave my answer just in case it can help somebody.

I know it is an old post, however here is an optimal solution in O(n): each element is moved exactly once and no extra space is needed. It is very similar to the solution proposed by @SomeStrangeUser but no requires gcd computation.

public static void shiftArray(int[] A, int k) {
    if (A.length == 0) {
        return;
    }
    k = k % A.length;
    k = (k + A.length) % A.length; // ensure k is positive
    if (k == 0) {
        return;
    }
    int i = 0, i0 = 0;
    int x = A[0];
    for (int u = 0; u < A.length; u++) { // count number of shifted elements
        int j = (i - k + A.length) % A.length; // ensure modulo is positive
        if (j == i0) { // end of a (sub-)cycle, advance to next one
            A[i] = x;
            x = A[i = ++i0];
        } else {
            A[i] = A[j];
            i = j;
        }
    }
}
import java.util.Scanner;

public class ArrayMoveByGivenSize {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        
        int[] A = new int[] {100,200,300,400,500,600};
        //movement = 2
        //output {500,600,100,200,300,400}

        System.out.println("Please enter the movement size");
        int s;
        Scanner sc = new Scanner(System.in);
        s= sc.nextInt();
        System.out.println(s);
        int[] X = new int[A.length];
        for (int i=0;i<A.length;i++)
        {
            if((i+s)<A.length)
            {
                X[i+s]=A[i];
            }
            else
            {
                X[(i+s) - A.length]=A[i] ;  
            }
            
        }
        for(int i =0;i<X.length ; i++)
        System.out.println(X[i]);
        
    }
}
Related