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:
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 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;
}
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 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#
// 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
<?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.
?>
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>
Producción
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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA