Dada una array A[] que consta de N enteros, la tarea es verificar si es posible reducir la array de al menos una longitud de 2 de modo que todos los elementos de la array sean iguales. En una operación, elija cualquier índice i y reemplace A[i] y A[i+1] con su valor XOR .
Ejemplo:
Entrada: A[] = {0, 2, 2}
Salida: SÍ
Explicación: Aplicar la operación dada para i=0 (indexación basada en cero). Por lo tanto, reemplace A[0] y A[1] por A[0]^A[1], es decir, 0^2->2. La array resultante es {2, 2} con todos los elementos iguales.Entrada: A[] = {2, 3, 1, 10}
Salida: NO
Explicación: No es posible que la array tenga todos los elementos iguales
Enfoque ingenuo: el problema anterior se puede resolver utilizando la observación de que la array dada se puede reducir a una array con dos elementos iguales o tres elementos iguales. A continuación se muestra el enfoque paso a paso para resolver el problema anterior:
- Cree una array de prefijos en la que el i -ésimo índice almacene el XOR de los elementos del índice 0 al i de la array A[] .
- Caso 1 donde la array se puede reducir a dos elementos iguales
- Supongamos que la array resultante es {X, X} . Dado que el XOR de todos los elementos de la array permanecerá constante, X^X=0=XOR( A[0…N-1]) . Este caso se puede manejar fácilmente verificando si el XOR de todos los elementos de la array es 0 .
- Caso 2 donde la array se puede reducir a tres elementos iguales
- Este caso puede manejarse iterando sobre todos los valores posibles de (i, j) tal que 0<= i < j <=N-1 y verificar si existe un valor de (i, j) tal que XOR(A[ 0…i]) = XOR(A[i+1…j]) = XOR(A[j+1…N]) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible
// to make all the array elements equal
// using the given operation
void possibleEqualArray(int A[], int N)
{
// Stores the prefix XOR array
vector<int> pref(N);
pref[0] = A[0];
for (int i = 1; i < N; i++) {
// Calculate prefix[i]
pref[i] = pref[i - 1] ^ A[i];
}
// Case 1, check if the XOR of
// the input array is 0
if (pref[N - 1] == 0) {
cout << "YES";
return;
}
// Case 2
// Iterate over all the ways to
// divide the array into three
// non empty subarrays
int cur_xor = 0;
for (int i = N - 1; i >= 0; i--) {
cur_xor ^= A[i];
for (int j = 0; j < i; j++) {
if (j) {
// XOR of Middle Block
int middle_xor
= pref[j - 1] ^ pref[i - 1];
// XOR of Left Block
int left_xor = pref[j - 1];
// XOR of Right Block
int right_xor = cur_xor;
if (left_xor == middle_xor
&& middle_xor == right_xor) {
cout << "YES";
return;
}
}
}
}
// Not Possible
cout << "NO";
}
// Driver Code
int main()
{
int A[] = { 0, 2, 2 };
int N = sizeof(A) / sizeof(int);
// Function Call
possibleEqualArray(A, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to check if it is possible
// to make all the array elements equal
// using the given operation
static void possibleEqualArray(int A[], int N)
{
// Stores the prefix XOR array
int[] pref= new int[N];
pref[0] = A[0];
for (int i = 1; i < N; i++) {
// Calculate prefix[i]
pref[i] = pref[i - 1] ^ A[i];
}
// Case 1, check if the XOR of
// the input array is 0
if (pref[N - 1] == 0) {
System.out.println("YES");
return;
}
// Case 2
// Iterate over all the ways to
// divide the array into three
// non empty subarrays
int cur_xor = 0;
for (int i = N - 1; i >= 0; i--) {
cur_xor ^= A[i];
for (int j = 0; j < i; j++) {
if (j!=0) {
// XOR of Middle Block
int middle_xor
= pref[j - 1] ^ pref[i - 1];
// XOR of Left Block
int left_xor = pref[j - 1];
// XOR of Right Block
int right_xor = cur_xor;
if (left_xor == middle_xor
&& middle_xor == right_xor) {
System.out.println( "YES");
return;
}
}
}
}
// Not Possible
System.out.println( "NO");
}
// Driver code
public static void main (String[] args)
{
int A[] = { 0, 2, 2 };
int N = A.length;
// Function Call
possibleEqualArray(A, N);
}
}
// This code is contributed by Potta Lokesh
Python3
# Python 3 Program of the above approach
# Function to check if it is possible
# to make all the array elements equal
# using the given operation
def possibleEqualArray(A, N):
# Stores the prefix XOR array
pref = [0 for i in range(N)]
pref[0] = A[0]
for i in range(1, N, 1):
# Calculate prefix[i]
pref[i] = pref[i - 1] ^ A[i]
# Case 1, check if the XOR of
# the input array is 0
if (pref[N - 1] == 0):
print("YES")
return
# Case 2
# Iterate over all the ways to
# divide the array into three
# non empty subarrays
cur_xor = 0
i = N - 1
while(i >= 0):
cur_xor ^= A[i]
for j in range(i):
if (j):
# XOR of Middle Block
middle_xor = pref[j - 1] ^ pref[i - 1]
# XOR of Left Block
left_xor = pref[j - 1]
# XOR of Right Block
right_xor = cur_xor
if (left_xor == middle_xor and middle_xor == right_xor):
print("YES")
return
i -= 1
# Not Possible
print("NO")
# Driver Code
if __name__ == '__main__':
A = [0, 2, 2]
N = len(A)
# Function Call
possibleEqualArray(A, N)
# This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to check if it is possible
// to make all the array elements equal
// using the given operation
static void possibleEqualArray(int []A, int N)
{
// Stores the prefix XOR array
int[] pref= new int[N];
pref[0] = A[0];
for (int i = 1; i < N; i++) {
// Calculate prefix[i]
pref[i] = pref[i - 1] ^ A[i];
}
// Case 1, check if the XOR of
// the input array is 0
if (pref[N - 1] == 0) {
Console.WriteLine("YES");
return;
}
// Case 2
// Iterate over all the ways to
// divide the array into three
// non empty subarrays
int cur_xor = 0;
for (int i = N - 1; i >= 0; i--) {
cur_xor ^= A[i];
for (int j = 0; j < i; j++) {
if (j!=0) {
// XOR of Middle Block
int middle_xor
= pref[j - 1] ^ pref[i - 1];
// XOR of Left Block
int left_xor = pref[j - 1];
// XOR of Right Block
int right_xor = cur_xor;
if (left_xor == middle_xor
&& middle_xor == right_xor) {
Console.WriteLine( "YES");
return;
}
}
}
}
// Not Possible
Console.WriteLine( "NO");
}
// Driver code
public static void Main(String[] args)
{
int []A = { 0, 2, 2 };
int N = A.Length;
// Function Call
possibleEqualArray(A, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript Program of the above approach
// Function to check if it is possible
// to make all the array elements equal
// using the given operation
function possibleEqualArray(A, N) {
// Stores the prefix XOR array
let pref = new Array(N);
pref[0] = A[0];
for (let i = 1; i < N; i++) {
// Calculate prefix[i]
pref[i] = pref[i - 1] ^ A[i];
}
// Case 1, check if the XOR of
// the input array is 0
if (pref[N - 1] == 0) {
document.write("YES");
return;
}
// Case 2
// Iterate over all the ways to
// divide the array into three
// non empty subarrays
let cur_xor = 0;
for (let i = N - 1; i >= 0; i--) {
cur_xor ^= A[i];
for (let j = 0; j < i; j++) {
if (j) {
// XOR of Middle Block
let middle_xor = pref[j - 1] ^ pref[i - 1];
// XOR of Left Block
let left_xor = pref[j - 1];
// XOR of Right Block
let right_xor = cur_xor;
if (left_xor == middle_xor && middle_xor == right_xor) {
document.write("YES");
return;
}
}
}
}
// Not Possible
document.write("NO");
}
// Driver Code
let A = [0, 2, 2];
let N = A.length;
// Function Call
possibleEqualArray(A, N);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
YES
Complejidad de tiempo: O(N 2 )
Complejidad de espacio: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la observación de que, en el caso de que la array se pueda reducir a los tres elementos iguales, la array resultante se puede representar como {X, X, X} . Dado que , (X^X^X) = XOR(A[0…N-1]) implica que X = XOR(A[0…N-1]) . El caso 1 se puede manejar de la misma manera que el enfoque ingenuo. El caso 2 se puede resolver de la siguiente manera:
- Inicialice cnt y cur_XOR en 0 y almacene el XOR de todos los elementos de A[] en tot_XOR .
- Itere sobre la array A[] y realice un seguimiento del XOR hasta el elemento actual en cur_XOR .
- Si cur_XOR = tot_XOR , incremente el cnt en 1 e inicialice cur_XOR = 0 .
- Después de recorrer todo el arreglo, si el valor de cnt > 2 , es posible igualar todos los elementos del arreglo usando la operación dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible
// to make all the array elements equal
// using the given operation
void possibleEqualArray(int A[], int N)
{
// Stores the XOR of all
// elements of array A[]
int tot_XOR = 0;
for (int i = 0; i < N; i++) {
tot_XOR ^= A[i];
}
// Case 1, check if the XOR of
// the array A[] is 0
if (tot_XOR == 0) {
cout << "YES";
return;
}
// Case 2
// Maintains the XOR till
// the current element
int cur_XOR = 0;
int cnt = 0;
// Iterate over the array
for (int i = 0; i < N; i++) {
cur_XOR ^= A[i];
// If the current XOR is equal
// to the total XOR increment
// the count and initialize
// current XOR as 0
if (cur_XOR == tot_XOR) {
cnt++;
cur_XOR = 0;
}
}
// Print Answer
if (cnt > 2) {
cout << "YES";
}
else {
cout << "NO";
}
}
// Driver Code
int main()
{
int A[] = { 0, 2, 2 };
int N = sizeof(A) / sizeof(int);
// Function Call
possibleEqualArray(A, N);
return 0;
}
Java
// Java Program of the above approach
import java.util.*;
class GFG{
// Function to check if it is possible
// to make all the array elements equal
// using the given operation
static void possibleEqualArray(int A[], int N)
{
// Stores the XOR of all
// elements of array A[]
int tot_XOR = 0;
for (int i = 0; i < N; i++) {
tot_XOR ^= A[i];
}
// Case 1, check if the XOR of
// the array A[] is 0
if (tot_XOR == 0) {
System.out.print("YES");
return;
}
// Case 2
// Maintains the XOR till
// the current element
int cur_XOR = 0;
int cnt = 0;
// Iterate over the array
for (int i = 0; i < N; i++) {
cur_XOR ^= A[i];
// If the current XOR is equal
// to the total XOR increment
// the count and initialize
// current XOR as 0
if (cur_XOR == tot_XOR) {
cnt++;
cur_XOR = 0;
}
}
// Print Answer
if (cnt > 2) {
System.out.print("YES");
}
else {
System.out.print("NO");
}
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 0, 2, 2 };
int N =( A.length);
// Function Call
possibleEqualArray(A, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 Program of the above approach
# Function to check if it is possible
# to make all the array elements equal
# using the given operation
def possibleEqualArray(A, N):
# Stores the XOR of all
# elements of array A[]
tot_XOR = 0
for i in range(N):
tot_XOR ^= A[i]
# Case 1, check if the XOR of
# the array A[] is 0
if (tot_XOR == 0):
print("YES")
return
# Case 2
# Maintains the XOR till
# the current element
cur_XOR = 0
cnt = 0
# Iterate over the array
for i in range(N):
cur_XOR ^= A[i]
# If the current XOR is equal
# to the total XOR increment
# the count and initialize
# current XOR as 0
if (cur_XOR == tot_XOR):
cnt += 1
cur_XOR = 0
# Print Answer
if (cnt > 2):
print("YES")
else:
print("NO")
# Driver Code
if __name__ == '__main__':
A = [0, 2, 2]
N = len(A)
# Function Call
possibleEqualArray(A, N)
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# Program of the above approach
using System;
class GFG{
// Function to check if it is possible
// to make all the array elements equal
// using the given operation
static void possibleEqualArray(int []A, int N)
{
// Stores the XOR of all
// elements of array A[]
int tot_XOR = 0;
for (int i = 0; i < N; i++) {
tot_XOR ^= A[i];
}
// Case 1, check if the XOR of
// the array A[] is 0
if (tot_XOR == 0) {
Console.Write("YES");
return;
}
// Case 2
// Maintains the XOR till
// the current element
int cur_XOR = 0;
int cnt = 0;
// Iterate over the array
for (int i = 0; i < N; i++) {
cur_XOR ^= A[i];
// If the current XOR is equal
// to the total XOR increment
// the count and initialize
// current XOR as 0
if (cur_XOR == tot_XOR) {
cnt++;
cur_XOR = 0;
}
}
// Print Answer
if (cnt > 2) {
Console.Write("YES");
}
else {
Console.Write("NO");
}
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 0, 2, 2 };
int N =( A.Length);
// Function Call
possibleEqualArray(A, N);
}
}
// This code is contributed by shivanisinghss2110.
Javascript
<script>
// JavaScript Program of the above approach
// Function to check if it is possible
// to make all the array elements equal
// using the given operation
function possibleEqualArray( A, N)
{
// Stores the XOR of all
// elements of array A[]
var tot_XOR = 0;
for (var i = 0; i < N; i++) {
tot_XOR ^= A[i];
}
// Case 1, check if the XOR of
// the array A[] is 0
if (tot_XOR == 0) {
document.write("YES");
return;
}
// Case 2
// Maintains the XOR till
// the current element
var cur_XOR = 0;
var cnt = 0;
// Iterate over the array
for (var i = 0; i < N; i++) {
cur_XOR ^= A[i];
// If the current XOR is equal
// to the total XOR increment
// the count and initialize
// current XOR as 0
if (cur_XOR == tot_XOR) {
cnt++;
cur_XOR = 0;
}
}
// Print Answer
if (cnt > 2) {
document.write("YES");
}
else {
document.write("NO");
}
}
// Driver Code
var A = [ 0, 2, 2 ];
var N =( A.length);
// Function Call
possibleEqualArray(A, N);
// This code is contributed by shivanisinghss2110
</script>
Producción:
YES
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA