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.
Examples :
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.
Method : Brute-force The brute force approach is to actually rotate the array for all given ranges, finally return the element in at given index in the modified array.
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.
Below is the implementation :
C++
// CPP code to rotate an array // and answer the index query #include <bits/stdc++.h> 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; } |
Java
// 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 code is contributed by Mr. Somesh Awasthi */ |
Python3
# Python 3 code to rotate an array # and answer the index query # Function to compute the element # at given index def findElement(arr, ranges, rotations, index) : for i in range(rotations - 1, -1, -1 ) : # Range[left...right] left = ranges[i][0] right = ranges[i][1] # Rotation will not have # any effect if (left <= index and right >= index) : if (index == left) : index = right else : index = index - 1 # Returning new element return arr[index] # Driver Code arr = [ 1, 2, 3, 4, 5 ] # No. of rotations rotations = 2 # Ranges according to # 0-based indexing ranges = [ [ 0, 2 ], [ 0, 3 ] ] index = 1 print(findElement(arr, ranges, rotations, index)) # This code is contributed by Nikita Tiwari. |
C#
// C# code to rotate an array // and answer the index query using System; 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 Code public static void Main () { 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; Console.Write(findElement(arr, ranges, rotations, index)); } } // This code is contributed // by nitin mittal. |
PHP
<?php // PHP code to rotate an array // and answer the index query // Function to compute the // element at given index function findElement($arr, $ranges, $rotations, $index) { for ($i = $rotations - 1; $i >= 0; $i--) { // Range[left...right] $left = $ranges[$i][0]; $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 Code $arr = array(1, 2, 3, 4, 5); // No. of rotations $rotations = 2; // Ranges according // to 0-based indexing $ranges = array(array(0, 2), array(0, 3)); $index = 1; echo findElement($arr, $ranges, $rotations, $index); // This code is contributed by ajit ?> |
Output :
3
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments