Find element at given index after a number of rotations
-
The author's code : An array consisting of N integers is given. There are several Right Circular Rotations of range[L..R] that we perform. After performing these rotations, we need to find element at a given index.
Quote:
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.
// CPP code to rotate an array
// and answer the index query
#include using namespace std;// Function to compute the element at
// given index
int findElement(int arr[], int ranges[][2],
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
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };// No. of rotations int rotations = 2; // Ranges according to 0-based indexing int ranges\[rotations\]\[2\] = { { 0, 2 }, { 0, 3 } }; int index = 1; cout << findElement(arr, ranges, rotations, index); return 0;}
Quote:
and the authors logic:
Method : Efficient We can do offline processing after saving all ranges. Suppose, our rotate ranges are : [0..2] and [0..3] We run through these ranges from reverse. After range [0..3], index 0 will have the element which was on index 3. So, we can change 0 to 3, i.e. if index = left, index will be changed to right. After range [0..2], index 3 will remain unaffected. So, we can make 3 cases : If index = left, index will be changed to right. If index is not bounds by the range, no effect of rotation. If index is in bounds, index will have the element at index-1. i tried buy brute fore method and it took O(n^2) time complexity. So i want to understand this logic, can someone please explain the logic. i have edited the information given, and it concludes all the information given by the
-
The author's code : An array consisting of N integers is given. There are several Right Circular Rotations of range[L..R] that we perform. After performing these rotations, we need to find element at a given index.
Quote:
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.
// CPP code to rotate an array
// and answer the index query
#include using namespace std;// Function to compute the element at
// given index
int findElement(int arr[], int ranges[][2],
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
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };// No. of rotations int rotations = 2; // Ranges according to 0-based indexing int ranges\[rotations\]\[2\] = { { 0, 2 }, { 0, 3 } }; int index = 1; cout << findElement(arr, ranges, rotations, index); return 0;}
Quote:
and the authors logic:
Method : Efficient We can do offline processing after saving all ranges. Suppose, our rotate ranges are : [0..2] and [0..3] We run through these ranges from reverse. After range [0..3], index 0 will have the element which was on index 3. So, we can change 0 to 3, i.e. if index = left, index will be changed to right. After range [0..2], index 3 will remain unaffected. So, we can make 3 cases : If index = left, index will be changed to right. If index is not bounds by the range, no effect of rotation. If index is in bounds, index will have the element at index-1. i tried buy brute fore method and it took O(n^2) time complexity. So i want to understand this logic, can someone please explain the logic. i have edited the information given, and it concludes all the information given by the
What is a "range" or a "rotate range?" When I hear the term rotate, I envision each element in the array could move one position to the left and the element that is in position 0 now moves to the N-1 position in the array. Similarly, each element in the array could move one position to the right and the element that is in position N-1 now moves to position 0 in the array. Am I way off?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
-
What is a "range" or a "rotate range?" When I hear the term rotate, I envision each element in the array could move one position to the left and the element that is in position 0 now moves to the N-1 position in the array. Similarly, each element in the array could move one position to the right and the element that is in position N-1 now moves to position 0 in the array. Am I way off?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
Yes it's an array rotation
In vino veritas
-
The author's code : An array consisting of N integers is given. There are several Right Circular Rotations of range[L..R] that we perform. After performing these rotations, we need to find element at a given index.
Quote:
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.
// CPP code to rotate an array
// and answer the index query
#include using namespace std;// Function to compute the element at
// given index
int findElement(int arr[], int ranges[][2],
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
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };// No. of rotations int rotations = 2; // Ranges according to 0-based indexing int ranges\[rotations\]\[2\] = { { 0, 2 }, { 0, 3 } }; int index = 1; cout << findElement(arr, ranges, rotations, index); return 0;}
Quote:
and the authors logic:
Method : Efficient We can do offline processing after saving all ranges. Suppose, our rotate ranges are : [0..2] and [0..3] We run through these ranges from reverse. After range [0..3], index 0 will have the element which was on index 3. So, we can change 0 to 3, i.e. if index = left, index will be changed to right. After range [0..2], index 3 will remain unaffected. So, we can make 3 cases : If index = left, index will be changed to right. If index is not bounds by the range, no effect of rotation. If index is in bounds, index will have the element at index-1. i tried buy brute fore method and it took O(n^2) time complexity. So i want to understand this logic, can someone please explain the logic. i have edited the information given, and it concludes all the information given by the
-
The author's code : An array consisting of N integers is given. There are several Right Circular Rotations of range[L..R] that we perform. After performing these rotations, we need to find element at a given index.
Quote:
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.
// CPP code to rotate an array
// and answer the index query
#include using namespace std;// Function to compute the element at
// given index
int findElement(int arr[], int ranges[][2],
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
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };// No. of rotations int rotations = 2; // Ranges according to 0-based indexing int ranges\[rotations\]\[2\] = { { 0, 2 }, { 0, 3 } }; int index = 1; cout << findElement(arr, ranges, rotations, index); return 0;}
Quote:
and the authors logic:
Method : Efficient We can do offline processing after saving all ranges. Suppose, our rotate ranges are : [0..2] and [0..3] We run through these ranges from reverse. After range [0..3], index 0 will have the element which was on index 3. So, we can change 0 to 3, i.e. if index = left, index will be changed to right. After range [0..2], index 3 will remain unaffected. So, we can make 3 cases : If index = left, index will be changed to right. If index is not bounds by the range, no effect of rotation. If index is in bounds, index will have the element at index-1. i tried buy brute fore method and it took O(n^2) time complexity. So i want to understand this logic, can someone please explain the logic. i have edited the information given, and it concludes all the information given by the
-
The logic is there in the code and description, maybe you need to read more of the book you are studying.
-
Please elaborate: it is not clear what you are trying to accomplish. Note: it could be NOT necessary to actually perform the rotations, you could possibly compute the result without actually rotate the array.
-
What is a "range" or a "rotate range?" When I hear the term rotate, I envision each element in the array could move one position to the left and the element that is in position 0 now moves to the N-1 position in the array. Similarly, each element in the array could move one position to the right and the element that is in position N-1 now moves to position 0 in the array. Am I way off?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
-
You are not rebuilding the array to match what it would look like after all the rotations. You are looking at a single index in the array. The logic applies to what is the effect of a rotation to that index alone - not the whole array.
Socialism is the Axe Body Spray of political ideologies: It never does what it claims to do, but people too young to know better keep buying it anyway. (Glenn Reynolds)