Dada una array binaria arr[] de tamaño N y un número entero K, la tarea es verificar si la array binaria se puede convertir en un palíndromo después de un número K de operaciones donde, en una sola operación, se puede elegir cualquier índice aleatorio y almacenar el valor. en el índice será reemplazado por su bit a bit XOR(^) con 1.
Ejemplos:
Entrada: arr[] = { 1, 0, 0, 1, 1}, K = 0
Salida: No
Explicación: Como la array no es un palíndromo, debemos necesitar un número de operaciones distinto de cero
para convertirlo en palíndromo.Entrada: arr[] = { 1, 0, 1, 1, 0, 0}, K = 1
Salida: Sí
Explicación: Arreglos más cercanos que son palíndromos: {0, 0, 1, 1, 0, 0} y {1 , 0, 1, 1, 0, 1}, lo cual es posible
usando solo 1 de tales operaciones.
Enfoque: El enfoque para resolver el problema se basa en la siguiente idea:
El número mínimo de operaciones requeridas es el número de elementos desiguales equidistantes de la mitad de la array y para hacerlos iguales se necesita 1 operación (de 1 a 0 o de 0 a 1 ).
Se necesitan 2 operaciones para cambiar dos elementos iguales y hacer que tengan el mismo valor nuevamente usando XOR bit a bit.
Para implementar esta idea, siga los pasos que se muestran a continuación:
- Inicialice dos punteros que apunten a los dos extremos de la array.
- Encuentre el número de elementos de array desiguales mientras atraviesa la array desde sus dos extremos.
- Si el número es mayor que K , entonces es imposible alcanzar el objetivo con exactamente K pasos.
- Si el número es exactamente igual a K , entonces es posible hacer que el arreglo sea un palíndromo.
- De lo contrario, si el número es menor que K :
- Si la longitud de la array es impar, cualquier número de K positivos está bien, ya que podemos realizar las operaciones en el índice medio.
- Si la longitud del arreglo es par, para que siga siendo un palíndromo, debemos elegir dos índices y hacer las operaciones sobre esos índices. Así que el K restante tiene que ser parejo.
Aquí está el código para el enfoque anterior:
C++
// C++ code for the approach
#include <bits/stdc++.h>
using namespace std;
// Function to check whether the array
// can be turned into palindrome after K
// number of operations
bool check_possibility(int* arr, int K)
{
// Store the length of the array in
// arr_length variable
int arr_length = sizeof(arr) / sizeof(
arr[0]);
// Initialize two pointers from left and
// right ends of the array
int i = 0;
int j = arr_length - 1;
// Keep iterating through the array from
// two ends until the two pointers cross
// each other to count the number
// of the different array items.
while (i < j) {
// If the two elements are unequal,
// decrease the value of K by one
if (arr[i] != arr[j]) {
K--;
}
// Move the left pointer towards the
// right and right pointer towards the
// left
i++;
j--;
}
// The unequal items are more than K or K
// becomes less than zero, it is impossible
// to make it a palindrome with D operations.
if (K < 0) {
return false;
}
// If K has a non-negative value, we make the
// array a palindrome if it has an odd length
// the remaining value of K is odd as we have
// to choose two indices at a time to keep it
// as a palindrome.
else {
if ((arr_length % 2) != 0
|| (K % 2) == 0) {
return true;
}
else {
return false;
}
}
}
// Driver code
int main()
{
int arr[6] = { 1, 0, 1, 1, 0, 0 };
int K = 1;
// Function call
if (check_possibility(arr, K) == true) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
return 0;
}
Java
// Java code for the approach
import java.io.*;
class GFG
{
// Function to check whether the array
// can be turned into palindrome after K
// number of operations
public static boolean check_possibility(int arr[],
int K)
{
// Store the length of the array in
// arr_length variable
int arr_length = arr.length;
// Initialize two pointers from left and
// right ends of the array
int i = 0;
int j = arr_length - 1;
// Keep iterating through the array from
// two ends until the two pointers cross
// each other to count the number
// of the different array items.
while (i < j) {
// If the two elements are unequal,
// decrease the value of K by one
if (arr[i] != arr[j]) {
K--;
}
// Move the left pointer towards the
// right and right pointer towards the
// left
i++;
j--;
}
// The unequal items are more than K or K
// becomes less than zero, it is impossible
// to make it a palindrome with D operations.
if (K < 0) {
return false;
}
// If K has a non-negative value, we make the
// array a palindrome if it has an odd length
// the remaining value of K is odd as we have
// to choose two indices at a time to keep it
// as a palindrome.
else {
if ((arr_length % 2) != 0 || (K % 2) == 0) {
return true;
}
else {
return false;
}
}
}
public static void main(String[] args)
{
int arr[] = { 1, 0, 1, 1, 0, 0 };
int K = 1;
// Function call
if (check_possibility(arr, K) == true) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
}
// This code is contributed by Rohit Pradhan
C#
// C# code for the approach
using System;
class GFG {
// Function to check whether the array
// can be turned into palindrome after K
// number of operations
static bool check_possibility(int[] arr, int K)
{
// Store the length of the array in
// arr_length variable
int arr_length = arr.Length;
// Initialize two pointers from left and
// right ends of the array
int i = 0;
int j = arr_length - 1;
// Keep iterating through the array from
// two ends until the two pointers cross
// each other to count the number
// of the different array items.
while (i < j) {
// If the two elements are unequal,
// decrease the value of K by one
if (arr[i] != arr[j]) {
K--;
}
// Move the left pointer towards the
// right and right pointer towards the
// left
i++;
j--;
}
// The unequal items are more than K or K
// becomes less than zero, it is impossible
// to make it a palindrome with D operations.
if (K < 0) {
return false;
}
// If K has a non-negative value, we make the
// array a palindrome if it has an odd length
// the remaining value of K is odd as we have
// to choose two indices at a time to keep it
// as a palindrome.
else {
if ((arr_length % 2) != 0 || (K % 2) == 0) {
return true;
}
else {
return false;
}
}
}
public static int Main()
{
int[] arr = new int[] { 1, 0, 1, 1, 0, 0 };
int K = 1;
// Function call
if (check_possibility(arr, K) == true) {
Console.WriteLine("Yes");
}
else {
Console.WriteLine("No");
}
return 0;
}
}
// This code is contributed by Taranpreet
Python3
# Python code for the approach
def check_possibility(arr, K):
# Store the length of the array in
# arr_length variable
arr_length = len(arr)
# Initialize two pointers from left and right
# ends of the array
i = 0
j = arr_length - 1
# Keep iterating through the array from two
# ends until the two pointers cross each
# other to count the number of the different
# array items.
while(i < j):
# If the two elements are unequal,
# decrease the value of K by one
if(arr[i] != arr[j]):
K -= 1
# Move the left pointer towards the right
# and right pointer towards the left
i += 1
j -= 1
# The unequal items are more than K or
# K becomes less than zero, it is impossible
# to make it a palindrome with K operations.
if(K < 0):
return False
# If K has a non-negative value, we make the
# array a palindrome if it has an odd length
# the remaining value of K is odd as we have
# to choose two indices at a time
# to keep it as a palindrome
else:
if( (arr_length % 2)!= 0 or (K % 2)== 0):
return True
else:
return False
# Driver code
if __name__ == '__main__':
arr = [1, 0, 1, 1, 0, 0]
K = 1
if check_possibility(arr, K) == True :
print("Yes")
else:
print("No")
Javascript
// JavaScript code for the approach
// Function to check whether the array
// can be turned into palindrome after K
// number of operations
function check_possibility(arr, K)
{
// Store the length of the array in
// arr_length variable
var arr_length = arr.length;
// Initialize two pointers from left and
// right ends of the array
var i = 0;
var j = arr_length - 1;
// Keep iterating through the array from
// two ends until the two pointers cross
// each other to count the number
// of the different array items.
while (i < j) {
// If the two elements are unequal,
// decrease the value of K by one
if (arr[i] != arr[j]) {
K--;
}
// Move the left pointer towards the
// right and right pointer towards the
// left
i++;
j--;
}
// The unequal items are more than K or K
// becomes less than zero, it is impossible
// to make it a palindrome with D operations.
if (K < 0) {
return false;
}
// If K has a non-negative value, we make the
// array a palindrome if it has an odd length
// the remaining value of K is odd as we have
// to choose two indices at a time to keep it
// as a palindrome.
else {
if ((arr_length % 2) != 0 || (K % 2) == 0) {
return true;
}
else {
return false;
}
}
}
// Driver code
var arr = [ 1, 0, 1, 1, 0, 0 ];
var K = 1;
// Function call
if (check_possibility(arr, K) == true) {
console.log("Yes");
}
else {
console.log("No");
}
// This code is contributed by phasing17
Producción
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shinjanpatra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA