programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Rotating array in right in k block

Ranch Hand
Posts: 954
4
• Number of slices to send:
Optional 'thank-you' note:
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:

my values are coming:

Bartender
Posts: 5465
212
• Number of slices to send:
Optional 'thank-you' note:
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:

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
Bartender
Posts: 5465
212
• 1
• Number of slices to send:
Optional 'thank-you' note:
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:

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

But what is wrong with this code?

Tushar Goel
Ranch Hand
Posts: 954
4
• Number of slices to send:
Optional 'thank-you' note:
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

Saloon Keeper
Posts: 10653
85
• 1
• Number of slices to send:
Optional 'thank-you' note:
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.

Tushar Goel
Ranch Hand
Posts: 954
4
• Number of slices to send:
Optional 'thank-you' note:

Carey Brown wrote:

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
Saloon Keeper
Posts: 10653
85
• Number of slices to send:
Optional 'thank-you' note:
You're welcome.

Piet Souris
Bartender
Posts: 5465
212
• Number of slices to send:
Optional 'thank-you' note:
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:

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

Tushar Goel
Ranch Hand
Posts: 954
4
• Number of slices to send:
Optional 'thank-you' note:

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:

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
Saloon Keeper
Posts: 10653
85
• Number of slices to send:
Optional 'thank-you' note:

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?

Marshal
Posts: 28138
95
• Number of slices to send:
Optional 'thank-you' note:
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
Ranch Hand
Posts: 954
4
• Number of slices to send:
Optional 'thank-you' note:

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:

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
Bartender
Posts: 5465
212
• 1
• Number of slices to send:
Optional 'thank-you' note:
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:

Marshal
Posts: 8850
636
• Number of slices to send:
Optional 'thank-you' note:

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
Ranch Hand
Posts: 954
4
• Number of slices to send:
Optional 'thank-you' note:
@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
Ranch Hand
Posts: 954
4
• Number of slices to send:
Optional 'thank-you' note:
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..

 Consider Paul's rocket mass heater.
reply
Similar Threads