Find original array from given array which is obtained after P prefix reversals | Set-2
Given an array arr[] of size N and an integer P, 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.
Note: P is less than or equal to N
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
Approach: The naive approach and two pointer approach is discussed in the Set-1 of this problem.
Mathematical observation based Approach: This approach is based on the mathematical observation shown below.
Consider the original array as arr[] and the reversed array after the P prefix reversals is rev[].
Now for an element in index i (0 based indexing):
- This element’s position is not affected for the first i moves (As it is the (i+1)th element of the array arr[]).
- So its position is affected (P-i) times in total.
- Now at the first move [i.e. the (i+1)th move ]in which it participates it becomes the first element of the modified array i.e. its index becomes 0. So movement towards left is (i – 0) = i and now it is the first element of the array.
- In the next move it becomes the last element of the (i+2) sized prefix and its index becomes (i+1) having a shift of (i+1) towards right.
- This shift keeps on happening for each alternate steps as it goes on becoming the 2nd element of prefix, then 2nd last of prefix and so on.
So from this it can be clearly seen that an element at ith index moves floor((P-i)/2) times towards right and ceil((P-i)/2) towards left as it starts alternating position with a left shift operation. Say floor((P-i)/2) = x and ceil((P-i)/2) = y
- If (P-i) = even, x = y
- If (P-i) = odd, y = x + 1
So the final position of an element at ith index of arr[] in the array rev[] can be calculated as: pos = i + [x*(i+1) – y*i]
- If (P-i) = even: pos = i + [x*i + x – x*i] = i+x
- If (P-i) = odd: pos = i + [x*i + x – (x + 1)*i] = x
Note: Only the indices in range [0, P-1] is obtained by this formula, the other elements remain as it is.
Follow the steps mentioned below to implement this approach:
- Initialize an array original[] of size N.
- Start iterating in a loop from i = 0 to N to fill the array original[].
- For each i in range [0, P-1] find the position of the ith element of original array in the given array by using the above formula.
- Fill the remaining elements as it is.
- Print the array original[].
Below is the implementation of the above approach.
C++
// 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
// 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. |
Python3
# 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 |
Javascript
<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#
// 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
Time Complexity: O(N)
Auxiliary Space: O(N)