We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Observe that at the 5th rotation, we got the original array again (a5 == a0).
In fact, at every N rotations we'll get the original array.
So, we don't need to rotate the array K times if K is greater than N. We can just rotate it (K%N) times (rest of integer division, or just 'modulo operation').
In my example 6%5 = 1.
And, even in this case, I don't need to actually rotate the array, but just retrieve an element from the array whose position is 1 lower than it was in the original array.
WHAT???
Yes, let's consider the initial array and after 1 or 6 rotations, as follows:
a0={0, 1, 2, 3, 4}
a1={4, 0, 1, 2, 3} (1st and 6th rotation)
If I try to retrieve the:
- 4th element, I'll get 3;
- 3rd element, I'll get 2, and so on.
Thus, if I subtract the number of rotations(K) from the index of the element, I'll get its value after K rotations, correct?
YES and NO!!!
a1[4] == a0[3]
a1[3] == a0[2]
Hummm... aK[m] == a0[m-(k%N)]! Great. No rotation is necessary, but just a simple calculation...
Let's continue...
Here we get an error type "Index out of bounds". It's because we are trying to acces memory positions that are out of the array's boundaries. Probably, it is being used by another variable.
A "Segmentation error" message may appear when K is much bigger than N (something like k=100000 and n=515, as in test case 4). It's because we are trying to acces memory positions that are out of the program boundaries and, probably, are being used by another application.
To correct these errors, we can use the same solution we used to simulate the K>N rotations: modulo operation!
The answer would be like this:
aK[m] == a0[(m+N-(K%N))%N].
We add N to the index to assure it will never be negative.
Tricky, fast and easy.
Try implementing this in your application.
That extra %N was added so that if our ans turns out to be greater than the number of elements in the array , the indexing should again start from index '0'.
eg. for m=1, our the later formula without using %N will result to 5.
but our ans should be equal to 0 and not 5 thats why we do modulus.
so that it could become 0
Circular Array Rotation
You are viewing a single comment's thread. Return to all comments →
Can anyone explain this easily from start ?
Well, let's try explain using an example case:
If I have an array(a) with, let's say, N=5 elements: a0=0, a1=1, a2=2, a3=3 and a4=4.
Let's consider that I have to rotate this array K=6 times.
So:
a0={0, 1, 2, 3, 4} (initial array)
When I right-rotate 6 times this array, following the rules estipulated in this problem, I'll get this:
a1={4, 0, 1, 2, 3} (1st rotation)
a2={3, 4, 0, 1, 2} (2nd rotation)
a3={2, 3, 4, 0, 1} (3th rotation)
a4={1, 2, 3, 4, 0} (4th rotation)
a5={0, 1, 2, 3, 4} (5th rotation)
a6={4, 0, 1, 2, 3} (6th rotation)
Observe that at the 5th rotation, we got the original array again (a5 == a0). In fact, at every N rotations we'll get the original array. So, we don't need to rotate the array K times if K is greater than N. We can just rotate it (K%N) times (rest of integer division, or just 'modulo operation'). In my example 6%5 = 1.
And, even in this case, I don't need to actually rotate the array, but just retrieve an element from the array whose position is 1 lower than it was in the original array.
WHAT???
Yes, let's consider the initial array and after 1 or 6 rotations, as follows:
a0={0, 1, 2, 3, 4}
a1={4, 0, 1, 2, 3} (1st and 6th rotation)
If I try to retrieve the:
- 4th element, I'll get 3;
- 3rd element, I'll get 2, and so on.
Thus, if I subtract the number of rotations(K) from the index of the element, I'll get its value after K rotations, correct?
YES and NO!!!
a1[4] == a0[3]
a1[3] == a0[2]
Hummm... aK[m] == a0[m-(k%N)]! Great. No rotation is necessary, but just a simple calculation...
Let's continue...
a1[2] == a0[1]
a1[1] == a0[0]
a1[0] == a0[-1] OPS! There's no a[-1]!!!
Here we get an error type "Index out of bounds". It's because we are trying to acces memory positions that are out of the array's boundaries. Probably, it is being used by another variable. A "Segmentation error" message may appear when K is much bigger than N (something like k=100000 and n=515, as in test case 4). It's because we are trying to acces memory positions that are out of the program boundaries and, probably, are being used by another application.
To correct these errors, we can use the same solution we used to simulate the K>N rotations: modulo operation!
The answer would be like this:
aK[m] == a0[(m+N-(K%N))%N].
We add N to the index to assure it will never be negative.
Tricky, fast and easy.
Try implementing this in your application.
I hope be helpful ;-)
Sorry, but in this line
aK[m] == a0[(m+N-(K%N))%N].
you %N again after +N for what purpose? If i think correctly, it's for rotate again the m index?
That extra %N was added so that if our ans turns out to be greater than the number of elements in the array , the indexing should again start from index '0'. eg. for m=1, our the later formula without using %N will result to 5. but our ans should be equal to 0 and not 5 thats why we do modulus. so that it could become 0
Best Approach ever! Hats off!