Dada una array arr[] de tamaño N , la tarea es comprobar si algún subarreglo de la array dada se puede convertir en un palíndromo reemplazando menos de la mitad de sus elementos (es decir , piso [longitud/2]) por cualquier otro elemento de la array. subarreglo
Ejemplos:
Entrada: arr[] = {2, 7, 4, 6, 7, 8}
Salida: Sí
Explicación: Entre todos los subarreglos de este arreglo, el subarreglo {7, 4, 6, 7} requiere solo 1 operación para convertirlo en un palíndromo es decir, reemplace arr[3] por 4 o arr[4] por 6, que es menor que floor(4/2) ( = 2).Entrada: arr[] = {3, 7, 19, 6}
Salida: No
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los subarreglos de la array dada y, para cada subarreglo, verificar si la cantidad de reemplazos necesarios para hacer que ese subarreglo sea un palíndromo es menor que el piso (longitud del subarreglo / 2) .
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
Si el arreglo arr[] contiene elementos duplicados, siempre es posible elegir un subarreglo desde la aparición inicial hasta la siguiente aparición de ese elemento. Este subarreglo requerirá menos operaciones de piso (longitud/2) ya que el primer y el último elemento del subarreglo ya son iguales.
Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa para almacenar las frecuencias de cada elemento del arreglo .
- Itere sobre todos los elementos de la array y cuente la frecuencia de cada elemento de la array e insértelo en el Mapa .
- Compruebe si la frecuencia de cualquier elemento de la array es mayor que 1. Si es cierto, imprima «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación de este enfoque:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// A Utility Function to check if a subarray
// can be palindromic by replacing less than
// half of the elements present in it
bool isConsistingSubarrayUtil(int arr[], int n)
{
// Stores frequency of array elements
map<int, int> mp;
// Traverse the array
for (int i = 0; i < n; ++i) {
// Update frequency of
// each array element
mp[arr[i]]++;
}
// Iterator over the Map
map<int, int>::iterator it;
for (it = mp.begin(); it != mp.end(); ++it) {
// If frequency of any element exceeds 1
if (it->second > 1) {
return true;
}
}
// If no repetition is found
return false;
}
// Function to check and print if any subarray
// can be made palindromic by replacing less
// than half of its elements
void isConsistingSubarray(int arr[], int N)
{
if (isConsistingSubarrayUtil(arr, N)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 3, 4, 5, 1 };
// Size of array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
isConsistingSubarray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// A Utility Function to check if a subarray
// can be palindromic by replacing less than
// half of the elements present in it
static boolean isConsistingSubarrayUtil(int arr[],
int n)
{
// Stores frequency of array elements
TreeMap<Integer,
Integer> mp = new TreeMap<Integer,
Integer>();
// Traverse the array
for(int i = 0; i < n; ++i)
{
// Update frequency of
// each array element
mp.put(arr[i],
mp.getOrDefault(arr[i], 0) + 1);
}
for(Map.Entry<Integer,
Integer> it : mp.entrySet())
{
// If frequency of any element exceeds 1
if (it.getValue() > 1)
{
return true;
}
}
// If no repetition is found
return false;
}
// Function to check and print if any subarray
// can be made palindromic by replacing less
// than half of its elements
static void isConsistingSubarray(int arr[], int N)
{
if (isConsistingSubarrayUtil(arr, N))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
// Driver Code
public static void main(String args[])
{
// Given array arr[]
int arr[] = { 1, 2, 3, 4, 5, 1 };
// Size of array
int N = arr.length;
// Function Call
isConsistingSubarray(arr, N);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach
# A Utility Function to check if a subarray
# can be palindromic by replacing less than
# half of the elements present in it
def isConsistingSubarrayUtil(arr, n) :
# Stores frequency of array elements
mp = {};
# Traverse the array
for i in range(n) :
# Update frequency of
# each array element
if arr[i] in mp :
mp[arr[i]] += 1;
else :
mp[arr[i]] = 1;
# Iterator over the Map
for it in mp :
# If frequency of any element exceeds 1
if (mp[it] > 1) :
return True;
# If no repetition is found
return False;
# Function to check and print if any subarray
# can be made palindromic by replacing less
# than half of its elements
def isConsistingSubarray(arr, N) :
if (isConsistingSubarrayUtil(arr, N)) :
print("Yes");
else :
print("No");
# Driver Code
if __name__ == "__main__" :
# Given array arr[]
arr = [ 1, 2, 3, 4, 5, 1 ];
# Size of array
N = len(arr);
# Function Call
isConsistingSubarray(arr, N);
# This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG{
// A Utility Function to check if a subarray
// can be palindromic by replacing less than
// half of the elements present in it
static bool isConsistingSubarrayUtil(int[] arr,
int n)
{
// Stores frequency of array elements
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Traverse the array
for(int i = 0; i < n; ++i)
{
// Update frequency of
// each array element
if (mp.ContainsKey(arr[i]) == true)
mp[arr[i]] += 1;
else
mp[arr[i]] = 1;
}
var val = mp.Keys.ToList();
foreach(var key in val)
{
// If frequency of any element exceeds 1
if (mp[key] > 1)
{
return true;
}
}
// If no repetition is found
return false;
}
// Function to check and print if any subarray
// can be made palindromic by replacing less
// than half of its elements
static void isConsistingSubarray(int[] arr, int N)
{
if (isConsistingSubarrayUtil(arr, N))
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
// Driver Code
public static void Main()
{
// Given array arr[]
int[] arr = { 1, 2, 3, 4, 5, 1 };
// Size of array
int N = arr.Length;
// Function Call
isConsistingSubarray(arr, N);
}
}
// This code is contributed by sanjoy62
Javascript
<script>
// Javascript program for the above approach
// A Utility Function to check if a subarray
// can be palindromic by replacing less than
// half of the elements present in it
function isConsistingSubarrayUtil(arr, n)
{
// Stores frequency of array elements
var mp = new Map();
// Traverse the array
for (var i = 0; i < n; ++i) {
// Update frequency of
// each array element
if(mp.has(arr[i]))
{
mp.set(arr[i], mp.get(arr[i])+1);
}
else
{
mp.set(arr[i], 1);
}
}
var ans = false;
// Iterator over the Map
mp.forEach((value, key) => {
// If frequency of any element exceeds 1
if (value > 1) {
ans = true;
}
});
if(ans)
return true;
// If no repetition is found
return false;
}
// Function to check and print if any subarray
// can be made palindromic by replacing less
// than half of its elements
function isConsistingSubarray(arr, N)
{
if (isConsistingSubarrayUtil(arr, N)) {
document.write( "Yes");
}
else {
document.write( "No" );
}
}
// Driver Code
// Given array arr[]
var arr = [1, 2, 3, 4, 5, 1];
// Size of array
var N = arr.length;
// Function Call
isConsistingSubarray(arr, N);
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)