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