# Find element at given index after a number of rotations

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.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `using` `namespace` `std; ` ` `  `// Function to compute the element at ` `// given index ` `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]; ` `        ``int` `right = ranges[i]; ` ` `  `        ``// 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] = { { 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

 `= 0; ``\$i``--)  ` `    ``{ ` ` `  `        ``// Range[left...right] ` `        ``\$left` `= ``\$ranges``[``\$i``]; ` `        ``\$right` `= ``\$ranges``[``\$i``]; ` ` `  `        ``// 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.

This article is attributed to GeeksforGeeks.org

## tags:

Arrays array-range-queries rotation Arrays

code

load comments