Find the original array from given array obtained after P prefix reversals

Last Updated : 05 Jul, 2023

Given an array arr[] of size N and an integer P (P < N), the task is to find the original array from the array obtained by P prefix reversals where in ith reversal the prefix of size i of the array containing indices in range [0, i-1] was reversed.

Examples:

Input: arr[] = {4, 2, 1, 3, 5, 6}, P = 4.
Output: 1 2 3 4 5 6
Explanation: {1, 2, 3, 4, 5, 6} on prefix reversal P = 1 converts to {1, 2, 3, 4, 5, 6}.
{1, 2, 3, 4, 5, 6} on prefix reversal P = 2 converts to {2, 1, 3, 4, 5, 6}.
{2, 1, 3, 4, 5, 6} on prefix reversal P = 3 converts to {3, 1, 2, 4, 5, 6}
{3, 1, 2, 4, 5, 6} on prefix reversal P = 4 converts to {4, 2, 1, 3, 5, 6}
So answer is {1, 2, 3, 4, 5, 6}

Input: arr[] = {10, 9, 8, 3, 5, 6}, P = 3
Output: 9 8 10 3 5 6

Naive Approach: To solve the problem reverse the prefix of size i in each step for i in range [1, P] starting from the P sized prefix and then gradually decrementing the size.

Algorithm

Initialize a pointer “end” to N-1.
For i in range [P, 1] do the following steps:
- Initialize a pointer “start” to i-1.
- While “start” is less than or equal to “end”, swap the elements at indices “start” and “end” and increment “start” and decrement “end”.
Reverse the entire array.

Implementation of the above approach

C++

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
vector<int> reverse_array(vector<int> arr, int n, int p) {
    for (int i = p; i > 0; i--) {
        reverse(arr.begin(), arr.begin() + i);
    }
    return arr;
}
 
int main() {
    vector<int> arr = {4, 2, 1, 3, 5, 6};
    int n = arr.size();
    int p = 4;
    vector<int> result = reverse_array(arr, n, p);
 
    for (int i = 0; i < n; i++) {
        cout << result[i] << " ";
    }
    cout << endl;
 
    return 0;
}

Java

import java.util.Arrays;
 
public class MyClass {
     
    public static int[] reverseArray(int[] arr, int n, int p) {
        for (int i = p; i > 0; i--) {
            int[] reversed = new int[i];
            for (int j = 0; j < i; j++) {
                reversed[j] = arr[j];
            }
            for (int j = 0; j < i / 2; j++) {
                int temp = reversed[j];
                reversed[j] = reversed[i - j - 1];
                reversed[i - j - 1] = temp;
            }
            for (int j = 0; j < i; j++) {
                arr[j] = reversed[j];
            }
        }
        return arr;
    }
 
    public static void main(String[] args) {
        int[] arr = {4, 2, 1, 3, 5, 6};
        int n = arr.length;
        int p = 4;
        int[] result = reverseArray(arr, n, p);
        System.out.println(Arrays.toString(result));
    }
}

Python

def reverse_array(arr, n, p):
    for i in range(p, 0, -1):
        arr[:i] = arr[:i][::-1]
    return arr
 
# Example usage
arr = [4, 2, 1, 3, 5, 6]
n = len(arr)
p = 4
result = reverse_array(arr, n, p)
print(result)

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
 
public class MainClass
{
    static List<int> reverse_array(List<int> arr, int n, int p)
    {
        for (int i = p; i > 0; i--)
        {
            arr.Reverse(0, i);
        }
        return arr;
    }
 
    public static void Main(string[] args)
    {
        List<int> arr = new List<int> { 4, 2, 1, 3, 5, 6 };
        int n = arr.Count;
        int p = 4;
        List<int> result = reverse_array(arr, n, p);
 
        foreach (int num in result)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
}
 
// This code is contributed by Pushpesh Raj

Javascript

// Javascript code for the above approach
// Define a function that reverses subarrays of an array
function reverseArray(arr, n, p) 
{
  for (let i = p; i > 0; i--) 
  {
   
    // Reverse the subarray arr[0...i-1] using slice, reverse, and concat methods
    arr = arr.slice(0, i).reverse().concat(arr.slice(i));
  }
  return arr;
}
 
// Define the main function
function main() {
  const arr = [4, 2, 1, 3, 5, 6];
  const n = arr.length;
  const p = 4;
  const result = reverseArray(arr, n, p);
  console.log(result.join(" "));
}
 
// Call the main function
main();

Output

[1, 2, 3, 4, 5, 6]

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: This solution is based on two pointer approach. Since there is only P prefix reversals, the first P elements of the array only gets affected remaining remains the same. So a pattern can be observed for the original and the array after P prefix reversals. Only the first P elements should be modified. Follow these steps to solve the above problem:

Initialize two variables l = 0 and r = P-1
Initialize a vector res to store the modified prefix and index = 0 to keep track of elements at odd and even indices.
Using a while loop iterate through the prefix of arr[].
- If the index is even push arr[l] into the vector res and increment l.
- Else push arr[r] into the vector res and decrement r.
- Increment the index also.
Now reverse the res and assign the modified prefix to the prefix of length p of arr.
Print the original array.

Below is the implementation of the above approach:

C++

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

// 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.

Python3

# 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#

// 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.

Javascript

<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>

Output

1 2 3 4 5 6

Time Complexity: O(N) where N is the length of the array.
Auxiliary Space: O(P) as the maximum size of res can be equal to P only. In a condition, when P=N, auxiliary space can reach to O(N)

Original Array from given Prefix Sums

lokeshpotta20

Improve

Article Tags :

Practice Tags :

Find the original array from given array obtained after P prefix reversals

C++

Java

Python

C#

Javascript

C++

Java

Python3

C#

Javascript

Similar Reads

Thank You!

What kind of Experience do you want to share?