An array consisting of N elements is given. There are several reversals we do in unique ranges[L..R]. The task is to print the element at given index.
Examples:
Input :
arr[] : 10 20 30 40 50
ranges[] = {{1, 4}, {0, 2}}
Query Index = 1
Output : 50
Explanation :
Reverse range[1..4] : 10 50 40 30 20
Reverse range[0..2] : 40 50 10 30 20
So we have 50 at index 1
The Brute Force approach would be to actually reverse a range of elements and answer the queries afterward.
Efficient Method: If we observe, the reversal of range[L..R] will result as follows :
The index will become right + left – index.
By doing this, we can compute the index easily.
Implementation:
C++
// Program to find index of an element after// given range reversals.#include <bits/stdc++.h>using namespace std;// Function to compute the element at query indexint answer(int arr[], int ranges[][2], int reversals, int index){ for (int i = reversals - 1; i >= 0; i--) { // Range[left...right] int left = ranges[i][0], right = ranges[i][1]; // If doesn't satisfy, reversal won't // have any effect if (left <= index && right >= index) index = right + left - index; } // Returning element at modified index return arr[index];}// Driverint main(){ int arr[] = { 10, 20, 30, 40, 50 }; // reversals int reversals = 2; int ranges[reversals][2] = { { 1, 4 }, { 0, 2 } }; int index = 1; cout << answer(arr, ranges, reversals, index); return 0;} |
Java
// Program to find index of an element// after given range reversals.import java.util.Arrays;class GFG { // Function to compute the element at // query index static int answer(int[] arr, int[][] ranges, int reversals, int index) { for (int i = reversals - 1; i >= 0; i--) { // Range[left...right] int left = ranges[i][0], right = ranges[i][1]; // If doesn't satisfy, reversal // won't have any effect if (left <= index && right >= index) index = right + left - index; } // Returning element at modified index return arr[index]; } // Driver code public static void main(String[] args) { int[] arr = { 10, 20, 30, 40, 50 }; // reversals int reversals = 2; int[][] ranges = { { 1, 4 }, { 0, 2 } }; int index = 1; System.out.println(answer(arr, ranges, reversals, index)); }}/* This code is contributed by Mr. Somesh Awasthi */ |
Python3
# Program to find index of an element # after given range reversals.# Function to compute the element# at query indexdef answer(arr, ranges, reversals, index): i = reversals - 1 while(i >= 0): # Range[left...right] left = ranges[i][0] right = ranges[i][1] # If doesn't satisfy, reversal won't # have any effect if (left <= index and right >= index): index = right + left - index i -= 1 # Returning element at modified index return arr[index]# Driver Codeif __name__ == '__main__': arr = [10, 20, 30, 40, 50] # reversals reversals = 2 ranges = [ [ 1, 4 ], [ 0, 2 ] ] index = 1 print(answer(arr, ranges, reversals, index))# This code is contributed by # Surendra_Gangwar |
C#
// C# program to find index of an element// after given range reversals.using System;class GFG { // Function to compute the element at // query index static int answer(int[] arr, int[, ] ranges, int reversals, int index) { for (int i = reversals - 1; i >= 0; i--) { // Range[left...right] int left = ranges[i, 0], right = ranges[i, 1]; // If doesn't satisfy, reversal // won't have any effect if (left <= index && right >= index) index = right + left - index; } // Returning element at modified index return arr[index]; } // Driver code public static void Main() { int[] arr = { 10, 20, 30, 40, 50 }; // reversals int reversals = 2; int[, ] ranges = { { 1, 4 }, { 0, 2 } }; int index = 1; Console.WriteLine(answer(arr, ranges, reversals, index)); }}// This code is contributed by vt_m. |
Javascript
<script> // Program to find index of an element // after given range reversals. // Function to compute the element at // query index function answer(arr, ranges, reversals, index) { for (let i = reversals - 1; i >= 0; i--) { // Range[left...right] let left = ranges[i][0], right = ranges[i][1]; // If doesn't satisfy, reversal // won't have any effect if (left <= index && right >= index) index = right + left - index; } // Returning element at modified index return arr[index]; } let arr = [ 10, 20, 30, 40, 50 ]; // reversals let reversals = 2; let ranges = [ [ 1, 4 ], [ 0, 2 ] ]; let index = 1; document.write(answer(arr, ranges, reversals, index)); </script> |
PHP
<?php// Program to find index // of an element after// given range reversals.// Function to compute the// element at query indexfunction answer($arr, $ranges, $reversals, $index){ for ($i = $reversals - 1; $i >= 0; $i--) { // Range[left...right] $left = $ranges[$i][0]; $right = $ranges[$i][1]; // If doesn't satisfy, // reversal won't have // any effect if ($left <= $index && $right >= $index) $index = $right + $left - $index; } // Returning element // at modified index return $arr[$index];}// Driver Code$arr = array( 10, 20, 30, 40, 50 );// reversals$reversals = 2;$ranges = array(array( 1, 4 ), array( 0, 2 ));$index = 1;echo answer($arr, $ranges, $reversals, $index);// This code is contributed // by nitin mittal.?> |
Output
50
Optimized solution
We can start by applying all the reversals to the array in the order they are given. To do this efficiently, we can use a helper function to reverse a given range of elements in the array. After applying all the reversals, we can answer the queries directly by accessing the element at the given index.
Algorithm
First define function reverseRange(arr, L, R) that takes an array arr such that
a.Two indices L and R as input.
If L < R, THAN swap the elements at indices L and R in the array arr.
After that Increment L and decrement R.
Define a function applyReversals(arr, ranges)
For each pair of indices (L, R) in ranges, call the reverseRange function with arguments (arr, L, R).
Define a function getElementAtIndex(arr, index)
Return the element of arr at index index.
Initialize an array arr and a list of ranges ranges.
Call the applyReversals and getElementAtIndex function
Assign the result to variable result.
Get result as output.
Implementation of above program
C++
#include <iostream>#include <vector>using namespace std;void reverseRange(vector<int>& arr, int L, int R) { while (L < R) { swap(arr[L], arr[R]); L++; R--; }}void applyReversals(vector<int>& arr, vector<pair<int, int>>& ranges) { for (int i = 0; i < ranges.size(); i++) { int L = ranges[i].first; int R = ranges[i].second; reverseRange(arr, L, R); }}int getElementAtIndex(vector<int>& arr, int index) { return arr[index];}int main() { // initialize inputs vector<int> arr = {10, 20, 30, 40, 50}; vector<pair<int, int>> ranges = {{1, 4}, {0, 2}}; int queryIndex = 1; // apply reversals and answer query applyReversals(arr, ranges); int result = getElementAtIndex(arr, queryIndex); // output result cout << result << endl; return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class ArrayReversalQuery { // Function to reverse a range of elements in the array public static void reverseRange(List<Integer> arr, int L, int R) { while (L < R) { int temp = arr.get(L); arr.set(L, arr.get(R)); arr.set(R, temp); L++; R--; } } // Function to apply a list of reversal ranges to the // array public static void applyReversals(List<Integer> arr, List<int[]> ranges) { for (int i = 0; i < ranges.size(); i++) { int L = ranges.get(i)[0]; int R = ranges.get(i)[1]; reverseRange(arr, L, R); } } // Function to get an element at a specific index in the // array public static int getElementAtIndex(List<Integer> arr, int index) { return arr.get(index); } public static void main(String[] args) { // Initialize inputs List<Integer> arr = new ArrayList<>(); arr.add(10); arr.add(20); arr.add(30); arr.add(40); arr.add(50); List<int[]> ranges = new ArrayList<>(); ranges.add(new int[] { 1, 4 }); // Reversal range 1 ranges.add(new int[] { 0, 2 }); // Reversal range 2 int queryIndex = 1; // Index for the query // Apply reversals to the array applyReversals(arr, ranges); // Get the element at the specified query index int result = getElementAtIndex(arr, queryIndex); // Output the result System.out.println(result); }} |
Python
def reverseRange(arr, L, R): while L < R: arr[L], arr[R] = arr[R], arr[L] L += 1 R -= 1def applyReversals(arr, ranges): for L, R in ranges: reverseRange(arr, L, R)def getElementAtIndex(arr, index): return arr[index]# initialize inputsarr = [10, 20, 30, 40, 50]ranges = [(1, 4), (0, 2)]queryIndex = 1# apply reversals and answer queryapplyReversals(arr, ranges)result = getElementAtIndex(arr, queryIndex)# output resultprint(result) |
C#
using System;using System.Collections.Generic;class Program { static void ReverseRange(List<int> arr, int L, int R) { while (L < R) { // Swap elements at indices L and R int temp = arr[L]; arr[L] = arr[R]; arr[R] = temp; L++; R--; } } static void ApplyReversals(List<int> arr, List<Tuple<int, int> > ranges) { foreach(var range in ranges) { int L = range.Item1; int R = range.Item2; ReverseRange(arr, L, R); } } static int GetElementAtIndex(List<int> arr, int index) { return arr[index]; } static void Main() { // Initialize inputs List<int> arr = new List<int>{ 10, 20, 30, 40, 50 }; List<Tuple<int, int> > ranges = new List<Tuple<int, int> >{ Tuple.Create(1, 4), Tuple.Create(0, 2) }; int queryIndex = 1; // Apply reversals and answer query ApplyReversals(arr, ranges); int result = GetElementAtIndex(arr, queryIndex); // Output result Console.WriteLine(result); }} |
Javascript
// Function to reverse a range [L, R] in an arrayfunction reverseRange(arr, L, R) { while (L < R) { // Swap elements at indices L and R [arr[L], arr[R]] = [arr[R], arr[L]]; L++; R--; }}// Function to apply a list of reversals to the given arrayfunction applyReversals(arr, ranges) { for (const range of ranges) { const L = range[0]; const R = range[1]; reverseRange(arr, L, R); }}// Function to get an element at a specific index in the arrayfunction getElementAtIndex(arr, index) { return arr[index];}// Main functionfunction main() { // Initialize inputs const arr = [10, 20, 30, 40, 50]; const ranges = [[1, 4], [0, 2]]; const queryIndex = 1; // Apply reversals and answer the query applyReversals(arr, ranges); const result = getElementAtIndex(arr, queryIndex); // Output the result console.log(result);}// Call the main function to execute the programmain(); |
Output
50
Time complexity O(N*M), where N is the length of the input array arr and M is the number of ranges in the input ranges.
Space complexity is O(1),as it does not use any additional memory.
This article is contributed by Rohit Thapliyal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
