Input : arr[] : {1, 2, 3, 4, 5}
ranges[] = { {0, 2}, {0, 3} }
index : 1
Output : 3
Explanation : After first given rotation {0, 2}
arr[] = {3, 1, 2, 4, 5}
After second rotation {0, 3}
arr[] = {4, 3, 1, 2, 5}
After all rotations we have element 3 at given index 1.
Not Able to Understand Why starting from last rotation gives right result but if we start from rotation 0 to last in loop it gives wrong result???
https://www.geeksforgeeks.org/find-element-given-index-number-rotations/
// Java code to rotate an array // and answer the index query
import java.util.*;
class GFG
{
// Function to compute the element at
// given index
static int findElement(int[] arr, int[][] ranges,
int rotations, int index)
{
for (int i = rotations - 1; i >= 0; i--) {
// Range[left...right]
int left = ranges[i][0];
int right = ranges[i][1];
// Rotation will not have any effect
if (left <= index && right >= index) {
if (index == left)
index = right;
else
index--;
}
}
// Returning new element
return arr[index];
}
// Driver
public static void main (String[] args) {
int[] arr = { 1, 2, 3, 4, 5 };
// No. of rotations
int rotations = 2;
// Ranges according to 0-based indexing
int[][] ranges = { { 0, 2 }, { 0, 3 } };
int index = 1;
System.out.println(findElement(arr, ranges,
rotations, index));
}
}
This will give right result but following will produce wrong result.
for (int i = 0; i < rotations; i++) {
// Range[left...right]
int left = ranges[i][0];
int right = ranges[i][1];
// Rotation will not have any effect
if (left <= index && right >= index) {
if (index == left)
index = right;
else
index--;
}
}
Lets us consider given 5 length array A1.
You have applied {0,2} rotation on A1. It is changed to A2.
You have applied {0,3} rotation on A2.. It is changed to A3
Now you are looking for output index 1 in A3 (which is {0,3} rotated on A2).
So Index 1 in A3 = Index 0 in A2 (as per the logic)
Now you are looking for Index 0 in A2 (which is {0,2} rotated on A1)
So Index 0 in A2 = Index 2 in A1 (as per the logic)
Hope this explanation clears why the rotations array is iterated in reverse way.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With