Given an array arr[] consisting of N integers, the task is to find the array K[] of minimum possible length such that after performing multiple mirror operations on K[], the given array arr[] can be obtained.
Mirror Operation: Appending all the array elements to the original array in reverse order.
Illustration:
arr[] = {1, 2, 3}
After 1st mirror operation, arr[] modifies to {1, 2, 3, 3, 2, 1}
After 2nd mirror operation, arr[] modifies to {1, 2, 3, 3, 2, 1, 1, 2, 3, 3, 2, 1}
Examples:
Input: N = 6, arr[] = { 1, 2, 3, 3, 2, 1 }
Output: 3
Explanation:
Subarrays {1, 2, 3} and {3, 2, 1} are mirror images of each other.
Single mirror operation on {1, 2, 3} obtains the given array.
Therefore, the minimum number of elements required is 3.
Input: N = 8, arr[] = { 1, 2, 2, 1, 1, 2, 2, 1 }
Output: 2
Explanation:
Subarrays {1, 2, 2, 1} and {1, 2, 2, 1} are mirror images of each other.
Subarray {1, 2} and {2, 1} are mirror images of each other.
{1, 2} -> {1, 2, 2, 1} -> {1, 2, 2, 1, 1, 2, 2, 1}
Therefore, the minimum number of elements required is 2.
Naive Approach:
The simplest approach to solve the problem is to generate all the possible subarrays from the given array of size less than equal to N/2 and, for each subarray, check if performing mirror operation gives the array arr[] or not. Print the minimum length subarray satisfying the condition. If no subarray is found to be satisfying, print No.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach:
The above approach can be further optimized using Divide and Conquer technique. Follow the steps below to solve the problem:
- Initialize a variable K = N and then, check whether the prefix of A[] of length K is a palindrome or not.
- If the prefix of length K is a palindrome then divide K by 2 and perform the above checking.
- If the prefix is not a palindrome then the answer is the current value of K.
- Keep checking while K > 0 until K is odd.
- If K is odd, then print the current value of K.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum number// of elements required to form A[]// by performing mirroring operationint minimumrequired(int A[], int N){ // Initialize K int K = N; int ans; while (K > 0) { // Odd length array // cannot be formed by // mirror operation if (K % 2 == 1) { ans = K; break; } bool ispalindrome = 1; // Check if prefix of // length K is palindrome for (int i = 0; i < K / 2; i++) { // Check if not a palindrome if (A[i] != A[K - 1 - i]) ispalindrome = 0; } // If found to be palindrome if (ispalindrome) { ans = K / 2; K /= 2; } // Otherwise else { ans = K; break; } } // Return the final answer return ans;}// Driver Codeint main(){ int a[] = { 1, 2, 2, 1, 1, 2, 2, 1 }; int N = sizeof a / sizeof a[0]; cout << minimumrequired(a, N); return 0;} |
Java
// Java Program to implement// the above approachclass GFG{ // Function to find minimum number// of elements required to form A[]// by performing mirroring operationstatic int minimumrequired(int A[], int N){ // Initialize K int K = N; int ans=0; while (K > 0) { // Odd length array // cannot be formed by // mirror operation if (K % 2 == 1) { ans = K; break; } int ispalindrome = 1; // Check if prefix of // length K is palindrome for (int i = 0; i < K / 2; i++) { // Check if not a palindrome if (A[i] != A[K - 1 - i]) ispalindrome = 0; } // If found to be palindrome if (ispalindrome == 1) { ans = K / 2; K /= 2; } // Otherwise else { ans = K; break; } } // Return the final answer return ans;} // Driver Codepublic static void main(String[] args){ int a[] = { 1, 2, 2, 1, 1, 2, 2, 1 }; int N = a.length; System.out.println(minimumrequired(a, N));}}// This code is contributed by rock_cool |
Python3
# Python3 program to implement # the above approach # Function to find minimum number # of elements required to form A[] # by performing mirroring operation def minimumrequired(A, N): # Initialize K K = N while (K > 0): # Odd length array # cannot be formed by # mirror operation if (K % 2) == 1: ans = K break ispalindrome = 1 # Check if prefix of # length K is palindrome for i in range(0, K // 2): # Check if not a palindrome if (A[i] != A[K - 1 - i]): ispalindrome = 0 # If found to be palindrome if (ispalindrome == 1): ans = K // 2 K = K // 2 # Otherwise else: ans = K break # Return the final answer return ans# Driver codeA = [ 1, 2, 2, 1, 1, 2, 2, 1 ]N = len(A)print(minimumrequired(A, N)) # This code is contributed by VirusBuddah_ |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to find minimum number// of elements required to form []A// by performing mirroring operationstatic int minimumrequired(int[] A, int N){ // Initialize K int K = N; int ans = 0; while (K > 0) { // Odd length array // cannot be formed by // mirror operation if (K % 2 == 1) { ans = K; break; } int ispalindrome = 1; // Check if prefix of // length K is palindrome for(int i = 0; i < K / 2; i++) { // Check if not a palindrome if (A[i] != A[K - 1 - i]) ispalindrome = 0; } // If found to be palindrome if (ispalindrome == 1) { ans = K / 2; K /= 2; } // Otherwise else { ans = K; break; } } // Return the readonly answer return ans;}// Driver Codepublic static void Main(String[] args){ int[] a = { 1, 2, 2, 1, 1, 2, 2, 1 }; int N = a.Length; Console.WriteLine(minimumrequired(a, N));}}// This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript Program to implement // the above approach // Function to find minimum number // of elements required to form A[] // by performing mirroring operation function minimumrequired(A, N) { // Initialize K let K = N; let ans; while (K > 0) { // Odd length array // cannot be formed by // mirror operation if (K % 2 == 1) { ans = K; break; } let ispalindrome = true; // Check if prefix of // length K is palindrome for (let i = 0; i < parseInt(K / 2, 10); i++) { // Check if not a palindrome if (A[i] != A[K - 1 - i]) ispalindrome = false; } // If found to be palindrome if (ispalindrome) { ans = parseInt(K / 2, 10); K = parseInt(K / 2, 10); } // Otherwise else { ans = K; break; } } // Return the final answer return ans; } let a = [ 1, 2, 2, 1, 1, 2, 2, 1 ]; let N = a.length; document.write(minimumrequired(a, N)); // This code is contributed by divyeshrabadiya07.</script> |
2
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
