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
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
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]);
}
}