Dada una array arr[] que consta de N enteros, la tarea es encontrar la array K[] de longitud mínima posible de modo que después de realizar múltiples operaciones de espejo en K[] , se pueda obtener la array arr[] dada.
Operación de espejo: agregar todos los elementos de la array a la array original en orden inverso.
Ilustración:
arr[] = {1, 2, 3}
Después de la primera operación de espejo, arr[] se modifica a {1, 2, 3, 3, 2, 1}
Después de la segunda operación de espejo, arr[] se modifica a {1 , 2, 3, 3, 2, 1, 1, 2, 3, 3, 2, 1}
Ejemplos:
Entrada: N = 6, arr[] = { 1, 2, 3, 3, 2, 1 }
Salida: 3
Explicación:
Los subarreglos {1, 2, 3} y {3, 2, 1} son imágenes especulares entre sí .
La operación de espejo único en {1, 2, 3} obtiene la array dada.
Por lo tanto, el número mínimo de elementos necesarios es 3.
Entrada: N = 8, arr[] = { 1, 2, 2, 1, 1, 2, 2, 1 }
Salida: 2
Explicación:
Subarreglos {1, 2, 2 , 1} y {1, 2, 2, 1} son imágenes especulares entre sí.
El subarreglo {1, 2} y {2, 1} son imágenes especulares entre sí.
{1, 2} -> {1, 2, 2, 1} -> {1, 2, 2, 1, 1, 2, 2, 1}
Por lo tanto, el número mínimo de elementos necesarios es 2.
Enfoque ingenuo:
el enfoque más simple para resolver el problema es generar todos los subarreglos posibles a partir del arreglo dado de tamaño menor que igual a N/2 y, para cada subarreglo, verificar si al realizar la operación espejo se obtiene el arreglo arr[] o no. Imprime el subarreglo de longitud mínima que cumple la condición. Si no se encuentra ningún subarreglo satisfactorio, imprima No .
Complejidad de tiempo: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente:
El enfoque anterior se puede optimizar aún más utilizando la técnica Divide and Conquer . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable K = N y luego verifique si el prefijo de A[] de longitud K es un palíndromo o no.
- Si el prefijo de longitud K es un palíndromo, divida K por 2 y realice la verificación anterior.
- Si el prefijo no es un palíndromo, la respuesta es el valor actual de K.
- Siga comprobando mientras K > 0 hasta que K sea impar.
- Si K es impar , imprima el valor actual de K.
A continuación se muestra la implementación del enfoque anterior:
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 operation
int 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 Code
int 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 approach
class GFG{
// Function to find minimum number
// of elements required to form A[]
// by performing mirroring operation
static 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 Code
public 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 code A = [ 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 approach
using System;
class GFG{
// Function to find minimum number
// of elements required to form []A
// by performing mirroring operation
static 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 Code
public 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
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por nishitsharma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA