Rotating array in right in k block

[Tushar Goel]

Hi,

I am working on a question in which i need to rotate an array right side by k steps. I am trying to use Juggling algorithm.
I got struck in odd case values (specially last and 2nd last values).

ex: say if i have an array like  [1,2,3,4,5,6,7,8}
so rotating 2 steps right means resultant array should be {7,8,1,2,3,4,5}.

I can do the same using brute force algo but need to optimize it.

Any guess where i am getting wrong? Here is my code:

	public static void rotateRight(int []inp, int k) {
		int size = inp.length;
		for (int i = 0; i < gcd(size, k); i++) {
		int j = size - i;
		int temp = inp[j - 1];
		while (true) {
			int d = (j - k) % size;
			
			if (d == i) break;
			
			inp[j - 1] = inp[d - 1];
			j = d;
		}
		
		inp[j - 1] = temp;
	  }
	}

	public static int gcd(int n, int b) {
		if (b == 0)
			return n;
		
		return gcd(b, n % b);


	public static void main(String[] args) {
		int []input = {1,2,3,4,5,6,7, 8};
		rotateRight(input, 2);
		System.out.println(Arrays.toString(input));
         }

my values are coming:  

[1, 8, 7, 2, 3, 4, 5, 6]

[Piet Souris]

Can you explain your algorithm, since it is not clear to me? Meanwhile, put some println's in your code, so that you can follow what is happening. For instance:

static void rotateRight(int[] inp, int k) {
    p(inp);
    int size = inp.length;
    for (int i = 0; i < gcd(size, k); i++) {
        int j = size - i;
        int temp = inp[j - 1];
        while (true) {
            int d = (j - k) % size;
            if (d == i) break;
            System.out.println("making element " + (j - i) + " equal to element " + (d - i));
            inp[j - 1] = inp[d - 1];
            p(inp);
            j = d;
        }
        inp[j - 1] = temp;
    }
}

private static void p(int[] array) {
    System.out.println("array: "+ Arrays.toString(array));
    System.out.println("*******************************");   
}

But there is little to optimize (in code? simplicity? run time?). You must perform as many translations as your array is long. There is a handy method in the Collections class that enables you to do the rotation without all that index juggling, at the cost of some performance, I think. But does a couple of milliseconds matter much?

[Piet Souris]

I understand your algo, although it is hard to say where it goes wrong. It is too simple, and when you save the rightmost element to the variable temp, you put that temp too early back into the array. Furthermore, your routine behaves reasonably with a shikt of 2, but fails for higher shifts. Lastly, whenever the shift is odd, the code crashes.

So here is the algo in my words (if wrong, let me know). Lets start with an array of length 7, and a shift of 3. For temporary storage, let Integer[] backup = new Integer[input.size]. Fiurthermore, to simplify the code, lets make shift to lie between 0 and size.
We do 3 blocks of shift, equal to the shift parameter (here 3), with blocknumbrs from 0 to 2
Within each block:
   let the index 'to' be equal to: size - 1 - blocknr
   let the index 'from' be equal to 'to - shift'
   save input[to] to backup: backup[(to + shift) % size = input[to]
   now, while (index from > 0) do:
       input[to] = input[from]
       to = from
       from -=k
    end while
next block
then, put the backup into input again
Code:

public static void rotateRight4(int[] a, int k) {
    Integer[] backup = new Integer[a.length];
    Arrays.fill(backup, null);
    int size = a.length;
    while (k < 0) k += size;
    k = k % size;
    p(a);
    for (int blocknr = 0; blocknr < k; blocknr++) {
        int to = size - 1 - blocknr;
        int from = to - k;
        int temp = a[to];
        while (from >= 0) {
            System.out.println("shifting element " + from + " to " + to);
            a[to] = a[from];
            to = from;
            p(a);
            from -= k;
        }
        backup[(size - 1 - blocknr + k) % size] = temp;
    }
    for (int i = 0; i < backup.length; i++) {
        if(backup[i] != null) a[i] = backup[i];
    }
}

private static void p(int[] array) {
    System.out.println("array: "+ Arrays.toString(array));
    System.out.println("*******************************");   
}

public static void main(String[] args) {
    int[] input = {1, 2, 3, 4, 5, 6, 7};
    rotateRight4(input, 3);
    System.out.println(Arrays.toString(input));
    System.out.println("**************************");
}

It should also work with a negative shift, so a rotateLeft.

But what is wrong with this code?

private static void rotateRight2(int[] a, int p) {
    var size = a.length;
    var b = Arrays.copyOf(a, size);
    IntStream.range(0, size).forEach(i -> a[(i + p) % size] = b[i]);
}

[Tushar Goel]

Thanks for the reply but i should mentioned to you i am not allowed to use extra array. Yes there are several different way to approach this problem like the way you mentioned, using recursive ops.

But for the learning prospective, i am trying to use algo which does take only constant space and solve it in o(n) time.

The original algo is used to rotate an array left wise but i am trying to use right side. So, i am not sure if it is possible to implement or not.

The actual algo is explained here in method 3, array_rotation

[Carey Brown]

I was not familiar with "Juggling" but a quick google turned up an example which was subtly different than yours and probably more efficient by a nano-second or two. Unfortunately it only did a rotate left, but you can implement rotate right using that.

	public static void rotateRight( int[] ary, int n )
	{
		rotateLeft( ary, ary.length - n );
	}

	public static void rotateLeft( int[] ary, int n )
	{
		// ...
    }

[Tushar Goel]

Carey Brown wrote:

	public static void rotateRight( int[] ary, int n )
	{
		rotateLeft( ary, ary.length - n );
	}

	public static void rotateLeft( int[] ary, int n )
	{
		// ...
    }

WOW.... it is so easy. I have not think that way. It can be done this way as well.... I have spent 2 days on it and solution was so simple...
Thank you...

[Carey Brown]

You're welcome.

[Piet Souris]

I totally underestimated the role of GCD. That made me having to save 'Shift' numbers, instead of just 1. Clever guys, these GeeksForGeeks!

But I never like methods that do a lot of this index juggling. It is often difficult to get it right and makes the code hard to follow. I mentioned a method in the Collections class, that we can use to let Java do all the hard work. The two problems (what are problems?) are that that method works with Lists, and therefore leaves the input array unmodified. But suppose we have two methods: List arrayToList(int[] array' and 'int[] listToArray(List list)' we could have:

private static int[] rotateRight3(int[] a, int shift) {
    var list = arrayToList(a);
    Collections.rotate(list, shift);
    return listToArray(list);
}

And 'shift' can be positive or negative, to detrmine the direction of the shift.

[Tushar Goel]

Piet Souris wrote:I totally underestimated the role of GCD. That made me having to save 'Shift' numbers, instead of just 1. Clever guys, these GeeksForGeeks!

But I never like methods that do a lot of this index juggling. It is often difficult to get it right and makes the code hard to follow. I mentioned a method in the Collections class, that we can use to let Java do all the hard work. The two problems (what are problems?) are that that method works with Lists, and therefore leaves the input array unmodified. But suppose we have two methods: List arrayToList(int[] array' and 'int[] listToArray(List list)' we could have:

private static int[] rotateRight3(int[] a, int shift) {
    var list = arrayToList(a);
    Collections.rotate(list, shift);
    return listToArray(list);
}

And 'shift' can be positive or negative, to detrmine the direction of the shift.

Actually i have checked Java 7 rotate method as well.. Internally they are using separate list to perform rotate but sometimes, we have to give a solution which is in place and takes constant memory.

But still i am unable to find out the problem in my original code. Not sure where i am wrong in that solution.

Meantime,i found another solution by recursive calls as mentioned in Programming Pearls.

[Carey Brown]

Tushar Goel wrote:Meantime,i found another solution by recursive calls as mentioned in Programming Pearls.

I'm curious. Could you post your code for that?

[Paul Clapham]

Without seeing the code I would guess that its purpose is to store the numbers being moved on the stack, thus sneakily circumventing the rule against storing them in another array.

[Tushar Goel]

Carey Brown wrote:

Tushar Goel wrote:Meantime,i found another solution by recursive calls as mentioned in Programming Pearls.

I'm curious. Could you post your code for that?

Here is the code, i have implemented:

	public static void rotateReversalAlgo(int []inp, int k) {
		reverse(inp, 0, inp.length - k - 1);
		reverse(inp, inp.length - k, inp.length - 1);
		reverse(inp, 0, inp.length - 1);
	}
	
	private static void reverse(int[] inp, int low, int high) {
		int left = low;
		int right = high;
		while (left <= right) {
			exchange(inp, left, right);
			left++;
			right--;
		}
		
	}

	private static void exchange(int[] inp, int low, int high) {
		int temp = inp[low];
		inp[low] = inp[high];
		inp[high] = temp;
	}

Actually in this we reverse array 3 times:
1) 0 to n-d-1 times  //so first time this reverse the array of length n-d
2) n-d to n times   //this will reverse the array of d length from end
3) 0 to n times // this again reverse the array so that elements comes to their position

[Piet Souris]

First of all, I have not looked at the replies so far, so I might bring old news that others already have explained.

Secondly: if I compare the code to my code in my previous reply, I see that they store 'shift' numbers as well, like I did, but they put them in the array as soon as possible, making it look like there is inly one number stored (in temp), while I stored them in an array, inputting them in the end. Hmmm...

As I said, I never liked this kind of solutions, with all that index juggling, they make it hard to follow what is going on. So, I suggest to look at two variants, and see how the process should go on.
But formost: you use the statement:
from = (j - k) % size;
Now, that is dangerous, since when j - k < 0, the result will also be negative, causing an IndexOutOfBoundError.
So, use
from = j - k;
if (from < 0) from += size;

Now, lets look at an array of length 8, and with a shift of 3 and a shift of 4, and see what should happen. I use more meaningful names than you used. Instead of j, I use 'to', instead of d, I use 'from', and insead of i, I use 'loopnr'.
And I refer to 'shift' as name for the shift taking place. It makes the code a little more readable. I also use the variable 'stop', that determines when a new loop should start. So here goes:

8, 3, gcd = 1
loopnr 0
to = size - 1 - loopnr = 7
temp = a[to]
stop = (to + shift) % size = 2
entering the loop, naming only the indices from and to for brevity
7 -> temp
4 -> 7
1 -> 4
6 -> 1
3 -> 6
0 -> 3
5 -> 0
2 -> 5
break the loop, since index 'from' = stop, so end with
temp -> 2
finished

Now for length 8, with shift 4, and gcd = 4
loop 0
to = size - 1 - loopnr = 7
stop = 3 (= (7 + shift) % 8
7 -> temp
3 -> 7
since 3 = stop break the loop
temp -> 3
loop 1
to = size - 1 - loopnr = 6
stop = 2
6 -> temp
2 -> 6
since 2 = stop, break the loop
temp -> 2
loop 2
to = 5
stop = 1
5 -> temp
1 -> 5
break the loop since 1 = stop
temp -> 1
loop 3
to = 4
stop = 0
4 -> temp
0 -> 4
break the loop
tmp -> 0
finished

Now, if we implement that in code, we get:

public static void rotateRight5(int[] a, int shift) {
    int from = 0, to = 0;
    int loopnr = 0;
    int size = a.length;
    int temp = 0, stop = 0;
    p(a);
    for (loopnr = 0; loopnr < gcd(size, shift); loopnr++) {
        to = size - 1 - loopnr;
        temp = a[to];
        stop = (to + shift) % size;
        System.out.format("new loop, loopnr = %d, to = %d, temp  = %d%n", loopnr, to, temp);
        while (true) {
            from = to - shift;
            if (from < 0) from += size;
            System.out.format("moving index %d to index %d, a[from] = %d, a[to] = %d%n", from, to, a[from], a[to]);
            a[to] = a[from];
            to = from;
            if (from == stop) break;
        }
        System.out.format("end of loopnr %d, moving temp to index %d %n", temp, a[from]);
        a[from] = temp;
    }
}

private static void p(int[] array) {
    System.out.println("array: "+ Arrays.toString(array));
    System.out.println("*******************************");   
}

[Liutauras Vilda]

Tushar Goel wrote:Meantime,i found another solution by recursive calls as mentioned in Programming Pearls.

Just not to mislead other readers. The solution you showed isn't recursive. In other words, it has no single recursive call.

Remind yourself what is the recursive function. A recursive function normally has two parts:

1. Stopping condition.
Processing the case(s) where the recursive function does not call itself.

2. Recursive step.
Processing the case(s) where the recursive function calls itself.

[Tushar Goel]

@Piet, Thanks for the nice and detailed explanation.. I have understood every single step you tried....

I was missing condition where i need to reset if from goes negative.. Anyway it was cool .. Thanks Again...


@Liutauras Vilda, Sorry for the confusion.. It was long time i have not involved in any serious coding.. So, i miss many points... Anyway, i am back now
and will have more discussion in coming days.. Sorry again for the confusion..

[Tushar Goel]

actually it teaches me 1 more thing.. importance of pencil and paper before jumping over the code..

I will try next time to emulate the steps on paper first..