Encuentre la array original de la array dada obtenida después de las inversiones del prefijo P

Dada una array arr[] de tamaño N y un entero P (P < N), la tarea es encontrar la array original a partir de la array obtenida por las inversiones de prefijos 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ó.

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 ingenuo: para resolver el problema, invierta el prefijo de tamaño i en cada paso para i en el rango [1, P] comenzando desde el prefijo de tamaño P y luego disminuyendo gradualmente el tamaño.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: esta solución se basa en un enfoque de dos punteros . Dado que solo hay inversiones de prefijo P , los primeros elementos P de la array solo se ven afectados y el resto permanece igual. Entonces, se puede observar un patrón para el original y la array después de las inversiones del prefijo P. Solo se deben modificar los primeros elementos P. Siga estos pasos para resolver el problema anterior:

• Inicializar dos variables l = 0 y r = P-1 
• Inicialice un vector res para almacenar el prefijo modificado y el índice = 0 para realizar un seguimiento de los elementos en índices pares e impares.
• Usando un ciclo while iterar a través del prefijo de arr[].
  • Si el índice es par, presione arr[l] en el vector res e incremente l .
  • De lo contrario, inserte arr[r]  en el vector res y disminuya r .
  • Incremente el índice también.
• Ahora invierta la res y asigne el prefijo modificado al prefijo de longitud p de arr.
• Imprime la array original.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
void find_original_array(int arr[], int n, int p)
{
    // Initialize the r and l
    int r = p - 1;
    int l = 0;
 
    // Initialize index = 0
    // to track elements at
    // odd and even positions
    int index = 0;
    vector<int> res;
 
    while (l <= r) {
 
        // If index is even
        if (index % 2 == 0) {
            res.push_back(arr[l++]);
        }
 
        // If index is odd
        else {
            res.push_back(arr[r--]);
        }
 
        // Increment index
        index = index + 1;
    }
 
    // Reverse the res
    reverse(res.begin(), res.end());
 
    // Assign the modified prefix to arr
    for (int i = 0; i < res.size(); i++) {
        arr[i] = res[i];
    }
 
    // Print the array arr
    // which is the original array
    // modified from the
    // prefix reversed array
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
}
 
// Driver code
int main()
{
 
    int arr[] = { 4, 2, 1, 3, 5, 6 }, P = 4;
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    find_original_array(arr, n, P);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
  static void find_original_array(int arr[], int n, int p)
  {
 
    // Initialize the r and l
    int r = p - 1;
    int l = 0;
 
    // Initialize index = 0
    // to track elements at
    // odd and even positions
    int index = 0;
    ArrayList<Integer> res = new ArrayList<Integer>();
 
    while (l <= r) {
 
      // If index is even
      if (index % 2 == 0) {
        res.add(arr[l++]);
      }
 
      // If index is odd
      else {
        res.add(arr[r--]);
      }
 
      // Increment index
      index = index + 1;
    }
 
    // Reverse the res
    Collections.reverse(res);
 
    // Assign the modified prefix to arr
    for (int i = 0; i < res.size(); i++) {
      arr[i] = (int)res.get(i);
    }
 
    // Print the array arr
    // which is the original array
    // modified from the
    // prefix reversed array
    for (int i = 0; i < n; i++) {
      System.out.print(arr[i] + " ");
    }
  }
 
  // Driver code
  public static void main(String args[])
  {
 
    int arr[] = { 4, 2, 1, 3, 5, 6 }, P = 4;
    int n = arr.length;
 
    // Function call
    find_original_array(arr, n, P);
 
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# Python program for the above approach
def find_original_array(arr, n, p):
 
    # Initialize the r and l
    r = p - 1;
    l = 0;
 
    # Initialize index = 0
    # to track elements at
    # odd and even positions
    index = 0;
    res = []
 
    while (l <= r):
 
        # If index is even
        if (index % 2 == 0):
            res.append(arr[l]);
            l += 1;
         
        # If index is odd
        else:
            res.append(arr[r]);
            r -= 1;
         
        # Increment index
        index = index + 1;
     
    # Reverse the res
    res.reverse();
 
    # Assign the modified prefix to arr
    for i in range(len(res)):
        arr[i] =  res[i];
     
    # Print array arr
    # which is the original array
    # modified from the
    # prefix reversed array
    for i in range(n):
        print(arr[i], end=" ");
     
# Driver code
if __name__ == '__main__':
 
    arr = [ 4, 2, 1, 3, 5, 6 ]
    P = 4;
    n = len(arr);
 
    # Function call
    find_original_array(arr, n, P);
 
# This code is contributed by gauravrajput1

// C# program for the above approach
using System;
using System.Collections;
 
class GFG
{
  static void find_original_array(int []arr, int n, int p)
  {
 
    // Initialize the r and l
    int r = p - 1;
    int l = 0;
 
    // Initialize index = 0
    // to track elements at
    // odd and even positions
    int index = 0;
    ArrayList res = new ArrayList();
 
    while (l <= r) {
 
      // If index is even
      if (index % 2 == 0) {
        res.Add(arr[l++]);
      }
 
      // If index is odd
      else {
        res.Add(arr[r--]);
      }
 
      // Increment index
      index = index + 1;
    }
 
    // Reverse the res
    res.Reverse();
 
    // Assign the modified prefix to arr
    for (int i = 0; i < res.Count; i++) {
      arr[i] = (int)res[i];
    }
 
    // Print the array arr
    // which is the original array
    // modified from the
    // prefix reversed array
    for (int i = 0; i < n; i++) {
      Console.Write(arr[i] + " ");
    }
  }
 
  // Driver code
  public static void Main()
  {
 
    int []arr = { 4, 2, 1, 3, 5, 6 };
    int P = 4;
    int n = arr.Length;
 
    // Function call
    find_original_array(arr, n, P);
 
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript program for the above approach
 
    const find_original_array = (arr, n, p) => {
     
        // Initialize the r and l
        let r = p - 1;
        let l = 0;
 
        // Initialize index = 0
        // to track elements at
        // odd and even positions
        let index = 0;
        let res = [];
 
        while (l <= r) {
 
            // If index is even
            if (index % 2 == 0) {
                res.push(arr[l++]);
            }
 
            // If index is odd
            else {
                res.push(arr[r--]);
            }
 
            // Increment index
            index = index + 1;
        }
 
        // Reverse the res
        res.reverse();
 
        // Assign the modified prefix to arr
        for (let i = 0; i < res.length; i++) {
            arr[i] = res[i];
        }
 
        // Print the array arr
        // which is the original array
        // modified from the
        // prefix reversed array
        for (let i = 0; i < n; i++) {
            document.write(`${arr[i]} `);
        }
    }
 
    // Driver code
    let arr = [4, 2, 1, 3, 5, 6], P = 4;
    let n = arr.length;
 
    // Function call
    find_original_array(arr, n, P);
 
// This code is contributed by rakeshsahni
 
</script>

1 2 3 4 5 6 

Complejidad de tiempo: O(N), donde N es la longitud de la array.
Espacio Auxiliar: O(N)