Encuentre el elemento en el índice dado después de las inversiones de rango dadas

Se da una array que consta de N elementos. Hay varias reversiones que hacemos en rangos únicos [L..R]. La tarea es imprimir el elemento en el índice dado.

Ejemplos: 

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

El enfoque de la fuerza bruta sería invertir una variedad de elementos y responder las consultas después.

Método eficiente: si observamos, la inversión de range[L..R] resultará de la siguiente manera: 
el índice se convertirá en right + left – index . 
Al hacer esto, podemos calcular el índice fácilmente. 

Implementación:

// 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 index
int 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];
}
 
// Driver
int 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;
}

// 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 */

# Program to find index of an element
# after given range reversals.
 
# Function to compute the element
# at query index
def 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 Code
if __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# 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.

<?php
// 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 ($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.
?>

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

50

Este artículo es una contribución de Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.