Encuentre la array original de la array dada que se obtiene después de las inversiones del prefijo P | Conjunto-2

Dada una array arr[] de tamaño N y un entero P , la tarea es encontrar la array original a partir de la array obtenida por las inversiones del prefijo P donde en la i-ésima inversión el prefijo de tamaño i de la array que contiene índices en el rango [0, i -1] se invirtió.

Nota: P es menor o igual que N

Ejemplos:

Entrada: arr[] = {4, 2, 1, 3, 5, 6}, P = 4.
Salida:  1 2 3 4 5 6
Explicación: {1, 2, 3, 4, 5, 6} en inversión de prefijo P = 1 se convierte en {1, 2, 3, 4, 5, 6}.
{1, 2, 3, 4, 5, 6} en la inversión del prefijo P = 2 se convierte en {2, 1, 3, 4, 5, 6}.
{2, 1, 3, 4, 5, 6} al invertir el prefijo P = 3 se convierte en {3, 1, 2, 4, 5, 6}
{3, 1, 2, 4, 5, 6} al invertir el prefijo P = 4 se convierte en {4, 2, 1, 3, 5, 6} 
Entonces la respuesta es {1, 2, 3, 4, 5, 6}

Entrada: arr[] = {10, 9, 8, 3, 5, 6}, P = 3
Salida: 9 8 10 3 5 6

Enfoque: El enfoque ingenuo y el enfoque de dos punteros se discuten en el Conjunto-1 de este problema.

Enfoque basado en la observación matemática: este enfoque se basa en la observación matemática que se muestra a continuación.

Considere la array original como arr[] y la array invertida después de las inversiones del prefijo P es rev[] .
Ahora, para un elemento en el índice i (indexación basada en 0) :

• La posición de este elemento no se ve afectada por los primeros movimientos i (ya que es el (i+1)-ésimo elemento de la array arr[]).
• Entonces su posición se ve afectada (Pi) veces en total.
• Ahora, en el primer movimiento [es decir, el (i+1)-ésimo movimiento] en el que participa, se convierte en el primer elemento de la array modificada, es decir, su índice se convierte en 0 . Entonces, el movimiento hacia la izquierda es (i – 0) = i y ahora es el primer elemento de la array.
• En el siguiente movimiento, se convierte en el último elemento del prefijo de tamaño (i+2) y su índice se convierte en (i+1) con un desplazamiento de (i+1) hacia la derecha .
• Este cambio continúa ocurriendo para cada paso alternativo a medida que se convierte en el segundo elemento del prefijo, luego en el segundo último del prefijo y así sucesivamente.

Entonces, a partir de esto, se puede ver claramente que un elemento en el i-ésimo índice se mueve piso ((Pi)/2) veces hacia la derecha y techo ((Pi)/2) hacia la izquierda cuando comienza a alternar posiciones con una operación de desplazamiento a la izquierda. Decir piso ((Pi)/2) = x y techo ((Pi)/2) = y

• Si (Pi) = par, x = y
• Si (Pi) = impar, y = x + 1

Entonces, la posición final de un elemento en el i-ésimo índice de arr[] en la array rev[] se puede calcular como: pos = i + [x*(i+1) – y*i]

• Si (Pi) = par : pos = i + [x*i + x – x*i] = i+x
• Si (Pi) = impar : pos = i + [x*i + x – (x + 1)*i] = x

Nota: Solo los índices en el rango [0, P-1] se obtienen con esta fórmula, los demás elementos permanecen como están.

Siga los pasos que se mencionan a continuación para implementar este enfoque:

• Inicialice una array original[] de tamaño N.
• Comience a iterar en un bucle desde i = 0 hasta N para llenar la array original[].
• Para cada i en el rango [0, P-1] encuentre la posición del i-ésimo elemento de la array original en la array dada usando la fórmula anterior.
• Rellene los elementos restantes tal como están.
• Imprime la array original[].

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

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the original array
void findOriginal(int arr[], int N, int P)
{
    int i, x;
    int original[N];
     
    // Loop to fill the original array
    for (i = 0; i < P; i++) {
        x = (P - i) / 2;
         
        // If (P-i) is odd
        if ((P - i) % 2)
            original[i] = arr[x];
         
        // If (P-i) is even
        else
            original[i] = arr[i + x];
    }
    for (i = P; i < N; i++)
        original[i] = arr[i];
 
    // Print the original array
    for (i = 0; i < N; i++)
        cout << original[i] << " ";
}
 
// Driver code
int main()
{
    int N = 6, P = 4;
    int arr[] = { 4, 2, 1, 3, 5, 6 };
     
    // Function call to get original array
    findOriginal(arr, N, P);
     
    return 0;
}

// Java code to implement above approach
class GFG {
 
  // Function to find the original array
  static void findOriginal(int arr[], int N, int P) {
    int i, x;
    int[] original = new int[N];
 
    // Loop to fill the original array
    for (i = 0; i < P; i++) {
      x = (P - i) / 2;
 
      // If (P-i) is odd
      if ((P - i) % 2 > 0)
        original[i] = arr[x];
 
      // If (P-i) is even
      else
        original[i] = arr[i + x];
    }
    for (i = P; i < N; i++)
      original[i] = arr[i];
 
    // Print the original array
    for (i = 0; i < N; i++)
      System.out.print(original[i] + " ");
  }
 
  // Driver code
  public static void main(String args[])
  {
    int N = 6, P = 4;
    int arr[] = { 4, 2, 1, 3, 5, 6 };
 
    // Function call to get original array
    findOriginal(arr, N, P);
  }
}
 
// This code is contributed by saurabh_jaiswal.

# python code to implement above approach
 
# Function to find the original array
def findOriginal(arr, N, P):
 
    original = [0 for _ in range(N)]
 
    # Loop to fill the original array
    for i in range(0, P):
        x = (P - i) // 2
 
        # If (P-i) is odd
        if ((P - i) % 2):
            original[i] = arr[x]
 
        # If (P-i) is even
        else:
            original[i] = arr[i + x]
 
    for i in range(P, N):
        original[i] = arr[i]
 
    # Print the original array
    for i in range(0, N):
        print(original[i], end=" ")
 
# Driver code
if __name__ == "__main__":
 
    N = 6
    P = 4
    arr = [4, 2, 1, 3, 5, 6]
 
    # Function call to get original array
    findOriginal(arr, N, P)
 
    # This code is contributed by rakeshsahni

<script>
       // JavaScript code for the above approach
 
       // Function to find the original array
       function findOriginal(arr, N, P) {
           let i, x;
           let original = new Array(N);
 
           // Loop to fill the original array
           for (i = 0; i < P; i++) {
               x = Math.floor((P - i) / 2);
 
               // If (P-i) is odd
               if ((P - i) % 2)
                   original[i] = arr[x];
 
               // If (P-i) is even
               else
                   original[i] = arr[i + x];
           }
           for (i = P; i < N; i++)
               original[i] = arr[i];
 
           // Print the original array
           for (i = 0; i < N; i++)
               document.write(original[i] + " ");
       }
 
       // Driver code
       let N = 6, P = 4;
       let arr = [4, 2, 1, 3, 5, 6];
 
       // Function call to get original array
       findOriginal(arr, N, P);
 
 // This code is contributed by Potta Lokesh
   </script>

// C# program for the above approach
using System;
class GFG
{
  // Function to find the original array
  static void findOriginal(int []arr, int N, int P) {
    int i, x;
    int []original = new int[N];
 
    // Loop to fill the original array
    for (i = 0; i < P; i++) {
      x = (P - i) / 2;
 
      // If (P-i) is odd
      if ((P - i) % 2 > 0)
        original[i] = arr[x];
 
      // If (P-i) is even
      else
        original[i] = arr[i + x];
    }
    for (i = P; i < N; i++)
      original[i] = arr[i];
 
    // Print the original array
    for (i = 0; i < N; i++)
      Console.Write(original[i] + " ");
  }
 
  // Driver code
  public static void Main()
  {
    int N = 6, P = 4;
    int []arr = { 4, 2, 1, 3, 5, 6 };
 
    // Function call to get original array
    findOriginal(arr, N, P);
  }
}
// This code is contributed by Samim Hossain Mondal.

1 2 3 4 5 6 

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