Consultas sobre el desplazamiento circular izquierdo y derecho en la array

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros. Hay tres tipos de comandos: 

  • 1 x: Circular a la derecha Desplaza la array x veces. Si una array es a[0], a[1], …., a[n – 1], luego de un desplazamiento circular a la derecha, la array se convertirá en a[n – 1], a[0], a[1] , …., un[n – 2].
  • 2 y: Circular a la izquierda Desplaza la array y veces. Si una array es a[0], a[1], …., a[n – 1], luego de un desplazamiento circular a la izquierda, la array se convertirá en a[1], …., a[n – 2], a [n-1], un[0].
  • 3 lr: Imprime la suma de todos los enteros en el subarreglo a[l…r] (l y r inclusive).

Dadas las consultas Q , la tarea es ejecutar cada consulta.

Ejemplos:

Entrada: N = 5, arr[] = { 1, 2, 3, 4, 5 },
consulta 1 = { 1, 3 }
consulta 2 = { 3, 0, 2 }
consulta 3 = { 2, 1 }
consulta 4 = { 3, 1, 4 }
Salida: 12,11
Explicación: Array inicial arr[] = { 1, 2, 3, 4, 5 } 
Después de la consulta 1, arr[] = { 3, 4, 5, 1, 2 }
Después de la consulta 2, la suma del índice 0 al índice 2 es 12, 
por lo que la salida 12.
Después de la consulta 3, arr[] = { 4, 5, 1, 2, 3 }
Después de la consulta 4, la suma del índice 1 al índice 4 es 11. 
Entonces salida 11.

Entrada: N = 5, arr[] = { 1, 2, 3, 4, 5 }
consulta 1 = { 2, 1 }
consulta 2 = { 3, 0, 2 }
consulta 3 = { 1, 3 }
consulta 4 = { 3, 1, 4 }
Salida: 9, 11 
Explicación:
array inicial arr[] = { 1, 2, 3, 4, 5 } 
Después de la consulta 1, arr[] = {2, 3, 4, 5, 1 }
Después de la consulta 2, la suma del índice 0 al índice 2 es 9. 
Entonces, la salida 9.
Después de la consulta 3, arr[] = { 4, 5, 1, 2, 3}
Después de la consulta 4, la suma del índice 1 al índice 4 es 11 Entonces 
salida 11.

Enfoque 1 (Enfoque bruto): La idea básica es la siguiente:

Para cada tipo de consulta, realice la tarea mencionada. En cada consulta, haga una rotación a la izquierda o a la derecha o encuentre la suma de los elementos en el rango dado.

Complejidad temporal: O(N * Q) donde Q es el número de consultas.
Espacio Auxiliar: O(1)

Enfoque 2 (Enfoque eficiente): El enfoque se basa en el concepto de suma de prefijos y rotación de array de la siguiente manera:

Inicialmente, la array no se gira. Entonces, calcule la rotación neta de la array. Una rotación neta negativa significa rotación a la derecha y una rotación neta positiva significa rotación a la izquierda. Siempre que haya una consulta que solicite la suma de un rango, proporcione la suma de los elementos que estarán en ese rango después de la rotación neta hasta ese índice.

Siga los siguientes pasos para implementar la idea:

  • Calcule la suma del prefijo de la array dada.
  • Solo necesitamos rastrear la rotación neta. 
    • Si el número rastreado es negativo, significa que la rotación a la izquierda ha dominado, de lo contrario, ha dominado la rotación a la derecha. 
    • Al rastrear las rotaciones netas, calcule el módulo de rotación neta N . 
  • Si existe la necesidad de responder alguna consulta de un tercer tipo y los límites son l y r : 
    • Encuentra lo que eran l y r en el orden original. 
    • Podemos averiguarlo fácilmente sumando las rotaciones netas al índice y tomando mod N . 
    • Use la array de suma de prefijos para encontrar la suma del rango dado en tiempo constante.

Siga la siguiente ilustración para una mejor comprensión:

Ilustración:

array inicial arr[] = { 1, 2, 3, 4, 5 } y las consultas son
consulta 1 = {2, 1}
consulta 2 = {3, 0, 2}
consulta 3 = {1, 3}
consulta 4 = {3, 1, 4}

El prefijo suma[] = { 1, 3, 6, 10, 15 } 

consulta 1 = {2, 1}: 
        => Rotación neta = 1

consulta 2 = { 3, 0, 2 }: 
        => Rotación neta = 1
        => Decir l = 0, r = 2.
        => Valor de l en el orden original = 1 y r en el orden original = 3.
        => Por lo tanto, la suma = 10 – 1 = 9 .

consulta 3 = {1, 3}:
        => Rotación neta = 1 – 3 = -2

consulta 4 = {3, 1, 4}:
        => Rotación neta = -2
        => Decir l = 1, r = 4.
        => Valor de l en orden original = (1 – 2 + 5)%5 = 4
        = > Valor de r en orden original = (4 – 2 + 5)%5 = 2
        => La suma = (15 – 10) + 6 = 11

A continuación se muestra la implementación del enfoque anterior:  

C++

// C++ Program to solve queries on Left and Right
// Circular shift on array
#include <bits/stdc++.h>
using namespace std;
 
// Function to solve query of type 1 x.
void querytype1(int* toRotate, int times, int n)
{
    // Decreasing the absolute rotation
    (*toRotate) = ((*toRotate) - times) % n;
}
 
// Function to solve query of type 2 y.
void querytype2(int* toRotate, int times, int n)
{
    // Increasing the absolute rotation.
    (*toRotate) = ((*toRotate) + times) % n;
}
 
// Function to solve queries of type 3 l r.
void querytype3(int toRotate, int l, int r, int preSum[],
                int n)
{
    // Finding absolute l and r.
    l = (l + toRotate + n) % n;
    r = (r + toRotate + n) % n;
 
    // if l is before r.
    if (l <= r)
        cout << (preSum[r + 1] - preSum[l]) << endl;
 
    // If r is before l.
    else
        cout << (preSum[n] + preSum[r + 1] - preSum[l])
             << endl;
}
 
// Wrapper Function solve all queries.
void wrapper(int a[], int n)
{
    int preSum[n + 1];
    preSum[0] = 0;
 
    // Finding Prefix sum
    for (int i = 1; i <= n; i++)
        preSum[i] = preSum[i - 1] + a[i - 1];
 
    int toRotate = 0;
 
    // Solving each query
    querytype1(&toRotate, 3, n);
    querytype3(toRotate, 0, 2, preSum, n);
    querytype2(&toRotate, 1, n);
    querytype3(toRotate, 1, 4, preSum, n);
}
 
// Driver Program
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    wrapper(arr, N);
    return 0;
}

Java

// Java Program to solve queries on Left and Right
// Circular shift on array
class GFG {
 
    // Function to solve query of type 1 x.
    static int querytype1(int toRotate, int times, int n)
    {
 
        // Decreasing the absolute rotation
        toRotate = (toRotate - times) % n;
        return toRotate;
    }
 
    // Function to solve query of type 2 y.
    static int querytype2(int toRotate, int times, int n)
    {
        // Increasing the absolute rotation.
        toRotate = (toRotate + times) % n;
        return toRotate;
    }
 
    // Function to solve queries of type 3 l r.
    static void querytype3(int toRotate, int l, int r,
                           int preSum[], int n)
    {
        // Finding absolute l and r.
        l = (l + toRotate + n) % n;
        r = (r + toRotate + n) % n;
 
        // if l is before r.
        if (l <= r)
            System.out.println(preSum[r + 1] - preSum[l]);
 
        // If r is before l.
        else
            System.out.println(preSum[n] + preSum[r + 1]
                               - preSum[l]);
    }
 
    // Wrapper Function solve all queries.
    static void wrapper(int a[], int n)
    {
        int preSum[] = new int[n + 1];
        preSum[0] = 0;
 
        // Finding Prefix sum
        for (int i = 1; i <= n; i++)
            preSum[i] = preSum[i - 1] + a[i - 1];
 
        int toRotate = 0;
 
        // Solving each query
        toRotate = querytype1(toRotate, 3, n);
        querytype3(toRotate, 0, 2, preSum, n);
        toRotate = querytype2(toRotate, 1, n);
        querytype3(toRotate, 1, 4, preSum, n);
    }
 
    // Driver Program
    public static void main(String args[])
    {
        int arr[] = { 1, 2, 3, 4, 5 };
        int N = arr.length;
        wrapper(arr, N);
    }
}
 
// This code is contributed by saurabh_jaiswal.

Python3

# Python Program to solve queries on Left and Right
# Circular shift on array
 
# Function to solve query of type 1 x.
def querytype1(toRotate, times, n):
   
    # Decreasing the absolute rotation
    toRotate = (toRotate - times) % n
    return toRotate
 
# Function to solve query of type 2 y.
def querytype2(toRotate, times, n):
   
    # Increasing the absolute rotation.
    toRotate = (toRotate + times) % n
    return toRotate
 
# Function to solve queries of type 3 l r.
def querytype3( toRotate, l, r, preSum, n):
   
    # Finding absolute l and r.
    l = (l + toRotate + n) % n
    r = (r + toRotate + n) % n
 
    # if l is before r.
    if (l <= r):
        print((preSum[r + 1] - preSum[l]))  
 
    # If r is before l.
    else:
        print((preSum[n] + preSum[r + 1] - preSum[l]))
 
# Wrapper Function solve all queries.
def wrapper( a, n):
    preSum = [ 0 for i in range(n + 1)]
     
    # Finding Prefix sum
    for i in range(1,n+1):
        preSum[i] = preSum[i - 1] + a[i - 1]
 
    toRotate = 0
 
    # Solving each query
    toRotate = querytype1(toRotate, 3, n)
    querytype3(toRotate, 0, 2, preSum, n)
    toRotate = querytype2(toRotate, 1, n)
    querytype3(toRotate, 1, 4, preSum, n);
 
# Driver Program
if __name__ == '__main__':
    arr = [ 1, 2, 3, 4, 5 ]
    N = len(arr)
    wrapper(arr, N)
 
# This code is contributed by rohan07.

C#

// C# Program to solve queries on Left and Right
// Circular shift on array
using System;
class GFG {
 
    // Function to solve query of type 1 x.
    static int querytype1(int toRotate, int times, int n)
    {
 
        // Decreasing the absolute rotation
        toRotate = (toRotate - times) % n;
        return toRotate;
    }
 
    // Function to solve query of type 2 y.
    static int querytype2(int toRotate, int times, int n)
    {
        // Increasing the absolute rotation.
        toRotate = (toRotate + times) % n;
        return toRotate;
    }
 
    // Function to solve queries of type 3 l r.
    static void querytype3(int toRotate, int l, int r,
                           int[] preSum, int n)
    {
        // Finding absolute l and r.
        l = (l + toRotate + n) % n;
        r = (r + toRotate + n) % n;
 
        // if l is before r.
        if (l <= r)
            Console.WriteLine(preSum[r + 1] - preSum[l]);
 
        // If r is before l.
        else
            Console.WriteLine(preSum[n] + preSum[r + 1]
                              - preSum[l]);
    }
 
    // Wrapper Function solve all queries.
    static void wrapper(int[] a, int n)
    {
        int[] preSum = new int[n + 1];
        preSum[0] = 0;
 
        // Finding Prefix sum
        for (int i = 1; i <= n; i++)
            preSum[i] = preSum[i - 1] + a[i - 1];
 
        int toRotate = 0;
 
        // Solving each query
        toRotate = querytype1(toRotate, 3, n);
        querytype3(toRotate, 0, 2, preSum, n);
        toRotate = querytype2(toRotate, 1, n);
        querytype3(toRotate, 1, 4, preSum, n);
    }
 
    // Driver Program
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        int N = arr.Length;
        wrapper(arr, N);
    }
}
 
// This code is contributed by _saurabh_jaiswal

Javascript

<script>
 
// JavaScript Program to solve queries on Left and Right
// Circular shift on array
 
// Function to solve query of type 1 x.
function querytype1(toRotate, times, n){
 
    // Decreasing the absolute rotation
    toRotate = (toRotate - times) % n
    return toRotate
}
 
// Function to solve query of type 2 y.
function querytype2(toRotate, times, n){
 
    // Increasing the absolute rotation.
    toRotate = (toRotate + times) % n
    return toRotate
}
 
// Function to solve queries of type 3 l r.
function querytype3( toRotate, l, r, preSum, n){
 
    // Finding absolute l and r.
    l = (l + toRotate + n) % n
    r = (r + toRotate + n) % n
 
    // if l is before r.
    if (l <= r)
        document.write((preSum[r + 1] - preSum[l]),"</br>")
 
    // If r is before l.
    else
        document.write((preSum[n] + preSum[r + 1] - preSum[l]),"</br>")
}
 
// Wrapper Function solve all queries.
function wrapper(a, n){
    preSum = new Array(n+1).fill(0)
 
    // Finding Prefix sum
    for(let i = 1; i <= n; i++)
        preSum[i] = preSum[i - 1] + a[i - 1]
 
    toRotate = 0
 
    // Solving each query
    toRotate = querytype1(toRotate, 3, n)
    querytype3(toRotate, 0, 2, preSum, n)
    toRotate = querytype2(toRotate, 1, n)
    querytype3(toRotate, 1, 4, preSum, n);
}
 
// Driver Program
let arr = [ 1, 2, 3, 4, 5 ]
let N = arr.length
wrapper(arr, N)
 
// This code is contributed by rohan07.
</script>
Producción

12
11

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por anuj0503 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *