Programa C++ para encontrar el elemento en el índice dado después de varias rotaciones

Se da una array que consta de N enteros. Hay varias rotaciones circulares derechas de rango [L..R] que realizamos. Después de realizar estas rotaciones, necesitamos encontrar el elemento en un índice dado.
Ejemplos: 
 

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. 

Método: fuerza bruta El enfoque de fuerza bruta consiste en rotar la array para todos los rangos dados y, finalmente, devolver el elemento en el índice dado en la array modificada.
Método: Eficiente Podemos hacer el procesamiento fuera de línea después de guardar todos los rangos. 
Supongamos que nuestros rangos de rotación son: [0..2] y [0..3] 
Corremos a través de estos rangos desde el revés.
Después del rango [0..3], el índice 0 tendrá el elemento que estaba en el índice 3. 
Entonces, podemos cambiar 0 a 3, es decir, si el índice = izquierda, el índice se cambiará a la derecha. 
Después del rango [0..2], el índice 3 no se verá afectado.
Entonces, podemos hacer 3 casos: 
si índice = izquierda, el índice se cambiará a la derecha. 
Si el índice no está limitado por el rango, no hay efecto de rotación. 
Si el índice está dentro de los límites, el índice tendrá el elemento en índice-1.
A continuación se muestra la implementación: 
 

Para una mejor explicación: –

10 20 30 40 50

Índice: 1

Rotaciones: {0,2} {1,4} {0,3}

Respuesta: el índice 1 tendrá 30 después de las 3 rotaciones en el orden {0,2} {1,4} {0,3}.

Realizamos {0,2} en A y ahora tenemos una nueva array A1.

Realizamos {1,4} en A1 y ahora tenemos una nueva array A2.

Realizamos {0,3} en A2 y ahora tenemos una nueva array A3.

Ahora estamos buscando el valor en el índice 1 en A3.

Pero A3 se hace {0,3} en A2.

Entonces, el índice 1 en A3 es el índice 0 en A2.

Pero A2 se hace {1,4} en A1.

Entonces, el índice 0 en A2 también es el índice 0 en A1, ya que no se encuentra en el rango {1,4}.

Pero A1 se hace {0,2} en A.

Entonces, el índice 0 en A1 es el índice 2 en A.

Al observarlo, vamos profundizando en las rotaciones anteriores a partir de la última rotación.

{0,3}

|

{1,4}

|

{0,2}

Esta es la razón por la que estamos procesando las rotaciones en orden inverso.

Tenga en cuenta que no estamos rotando los elementos en el orden inverso, solo procesando el índice al revés.

Porque si realmente rotamos en orden inverso, podríamos obtener una respuesta completamente diferente, ya que en el caso de las rotaciones, el orden importa. 

// 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;
 
}

Producción : 

3

Complejidad de tiempo: O(N), donde N representa el número dado de rotaciones.

Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.

¡ Consulte el artículo completo sobre Buscar elemento en el índice dado después de varias rotaciones para obtener más detalles!