Dada una array arr[] de tamaño N , la tarea es encontrar todos los tripletes (i, j, k) de modo que reemplace los elementos de los tripletes con sus valores Bitwise XOR , es decir, reemplace arr[i], arr[j] , arr[k] con (arr[i] ^ arr[j] ^ arr[k]) hace que todos los elementos de la array sean iguales. Si existe más de una solución, imprima cualquiera de ellas. De lo contrario, imprima -1 .
Ejemplos:
Entrada: arr[] = { 4, 2, 1, 7, 2 }
Salida: { (0, 1, 2), (2, 3, 4), (0, 1, 4) }
Explicación:
Seleccionar un triplete ( 0, 1, 2) y reemplazándolos con arr[0] ^ arr[1] ^ arr[2] modifica arr[] a { 7, 7, 7, 7, 2 }
Seleccionando un triplete (2, 3, 4) y reemplazándolos con arr[2] ^ arr[3] ^ arr[4] modifica arr[] a { 7, 7, 2, 2, 2 }
Seleccionando un triplete (0, 1, 4) y reemplazándolos con arr[ 0] ^ arr[1] ^ arr[2] modifica arr[] a { 2, 2, 2, 2, 2 }Entrada: arr[] = { 1, 3, 2, 2 }
Salida: -1
Planteamiento: El problema se puede resolver con base en la siguiente observación:
x ^ X ^ Y = Y
X ^ Y ^ Y = X
Si dos elementos cualesquiera de un triplete son iguales, al reemplazar todos los elementos del triplete con su Bitwise XOR , todos los elementos del triplete son iguales al tercer elemento del triplete .
Siga los pasos a continuación para resolver el problema:
- Seleccionando los tripletes de la forma { (0, 1, 2) , (2, 3, 4) …} hace que los elementos de los pares { (arr[0], arr[1]) , (arr[2], arr [3]) … } igual.
- De las observaciones anteriores, seleccionando los tripletes de la forma { (0, 1, N – 1) , (2, 3, N -1) , … } hace que todos los elementos del arreglo sean iguales al último elemento del arreglo.
- Finalmente, imprima los tripletes.
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 triplets such that
// replacing them with their XOR make
// all array elements equal
void checkXOR(int arr[], int N)
{
// If N is even
if (N % 2 == 0) {
// Calculate xor of
// array elements
int xro = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update xor
xro ^= arr[i];
}
// If xor is not equal to 0
if (xro != 0) {
cout << -1 << endl;
return;
}
// Selecting the triplets such that
// elements of the pairs (arr[0], arr[1]),
// (arr[2], arr[3])... can be made equal
for (int i = 0; i < N - 3; i += 2) {
cout << i << " " << i + 1
<< " " << i + 2 << endl;
}
// Selecting the triplets such that
// all array elements can be made
// equal to arr[N - 1]
for (int i = 0; i < N - 3; i += 2) {
cout << i << " " << i + 1
<< " " << N - 1 << endl;
}
}
else {
// Selecting the triplets such that
// elements of the pairs (arr[0], arr[1]),
// (arr[2], arr[3])... can be made equal
for (int i = 0; i < N - 2; i += 2) {
cout << i << " " << i + 1 << " "
<< i + 2 << endl;
}
// Selecting the triplets such that
// all array elements can be made
// equal to arr[N - 1]
for (int i = 0; i < N - 2; i += 2) {
cout << i << " " << i + 1
<< " " << N - 1 << endl;
}
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 4, 2, 1, 7, 2 };
// Size of array
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
checkXOR(arr, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find triplets such that
// replacing them with their XOR make
// all array elements equal
static void checkXOR(int arr[], int N)
{
// If N is even
if (N % 2 == 0)
{
// Calculate xor of
// array elements
int xro = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update xor
xro ^= arr[i];
}
// If xor is not equal to 0
if (xro != 0)
{
System.out.println(-1);
return;
}
// Selecting the triplets such that
// elements of the pairs (arr[0], arr[1]),
// (arr[2], arr[3])... can be made equal
for(int i = 0; i < N - 3; i += 2)
{
System.out.println(i + " " + (i + 1) +
" " + (i + 2));
}
// Selecting the triplets such that
// all array elements can be made
// equal to arr[N - 1]
for(int i = 0; i < N - 3; i += 2)
{
System.out.println(i + " " + (i + 1) +
" " + (N - 1));
}
}
else
{
// Selecting the triplets such that
// elements of the pairs (arr[0], arr[1]),
// (arr[2], arr[3])... can be made equal
for(int i = 0; i < N - 2; i += 2)
{
System.out.println(i + " " + (i + 1) +
" " + (i + 2));
}
// Selecting the triplets such that
// all array elements can be made
// equal to arr[N - 1]
for(int i = 0; i < N - 2; i += 2)
{
System.out.println(i + " " + (i + 1) +
" " + (N - 1));
}
}
}
// Driver code
public static void main(String[] args)
{
// Given array
int arr[] = { 4, 2, 1, 7, 2 };
// Size of array
int N = arr.length;
// Function call
checkXOR(arr, N);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python program to implement # the above approach # Function to find triplets such that # replacing them with their XOR make # all array elements equal def checkXOR(arr, N): # If N is even if (N % 2 == 0): # Calculate xor of # array elements xro = 0; # Traverse the array for i in range(N): # Update xor xro ^= arr[i]; # If xor is not equal to 0 if (xro != 0): print(-1); return; # Selecting the triplets such that # elements of the pairs (arr[0], arr[1]), # (arr[2], arr[3])... can be made equal for i in range(0, N - 3, 2): print(i, " ", (i + 1), " ", (i + 2), end=" "); # Selecting the triplets such that # all array elements can be made # equal to arr[N - 1] for i in range(0, N - 3, 2): print(i, " ", (i + 1), " ", (N - 1), end=" "); else: # Selecting the triplets such that # elements of the pairs (arr[0], arr[1]), # (arr[2], arr[3])... can be made equal for i in range(0, N - 2, 2): print(i, " ", (i + 1), " ", (i + 2)); # Selecting the triplets such that # all array elements can be made # equal to arr[N - 1] for i in range(0, N - 2, 2): print(i, " ", (i + 1), " ", (N - 1)); # Driver code if __name__ == '__main__': # Given array arr = [4, 2, 1, 7, 2]; # Size of array N = len(arr); # Function call checkXOR(arr, N); # This code is contributed by 29AjayKumar
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find triplets such that
// replacing them with their XOR make
// all array elements equal
static void checkXOR(int[] arr, int N)
{
// If N is even
if (N % 2 == 0)
{
// Calculate xor of
// array elements
int xro = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update xor
xro ^= arr[i];
}
// If xor is not equal to 0
if (xro != 0)
{
Console.WriteLine(-1);
return;
}
// Selecting the triplets such that
// elements of the pairs (arr[0], arr[1]),
// (arr[2], arr[3])... can be made equal
for(int i = 0; i < N - 3; i += 2)
{
Console.WriteLine(i + " " + (i + 1) +
" " + (i + 2));
}
// Selecting the triplets such that
// all array elements can be made
// equal to arr[N - 1]
for(int i = 0; i < N - 3; i += 2)
{
Console.WriteLine(i + " " + (i + 1) +
" " + (N - 1));
}
}
else
{
// Selecting the triplets such that
// elements of the pairs (arr[0], arr[1]),
// (arr[2], arr[3])... can be made equal
for(int i = 0; i < N - 2; i += 2)
{
Console.WriteLine(i + " " + (i + 1) +
" " + (i + 2));
}
// Selecting the triplets such that
// all array elements can be made
// equal to arr[N - 1]
for(int i = 0; i < N - 2; i += 2)
{
Console.WriteLine(i + " " + (i + 1) +
" " + (N - 1));
}
}
}
// Driver code
public static void Main()
{
// Given array
int[] arr = { 4, 2, 1, 7, 2 };
// Size of array
int N = arr.Length;
// Function call
checkXOR(arr, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find triplets such that
// replacing them with their XOR make
// all array elements equal
function checkXOR(arr, N)
{
// If N is even
if (N % 2 == 0) {
// Calculate xor of
// array elements
let xro = 0;
// Traverse the array
for (let i = 0; i < N; i++) {
// Update xor
xro ^= arr[i];
}
// If xor is not equal to 0
if (xro != 0) {
document.write(-1 + "<br>");
return;
}
// Selecting the triplets such that
// elements of the pairs (arr[0], arr[1]),
// (arr[2], arr[3])... can be made equal
for (let i = 0; i < N - 3; i += 2) {
document.write(i + " " + (i + 1)
+ " " + (i + 2) + "<br>");
}
// Selecting the triplets such that
// all array elements can be made
// equal to arr[N - 1]
for (let i = 0; i < N - 3; i += 2) {
document.write(i + " " + (i + 1)
+ " " + (N - 1) + "<br>");
}
}
else {
// Selecting the triplets such that
// elements of the pairs (arr[0], arr[1]),
// (arr[2], arr[3])... can be made equal
for (let i = 0; i < N - 2; i += 2) {
document.write(i + " " + (i + 1) + " "
+ (i + 2) + "<br>");
}
// Selecting the triplets such that
// all array elements can be made
// equal to arr[N - 1]
for (let i = 0; i < N - 2; i += 2) {
document.write(i + " " + (i + 1)
+ " " + (N - 1) + "<br>");
}
}
}
// Driver Code
// Given array
let arr = [ 4, 2, 1, 7, 2 ];
// Size of array
let N = arr.length;
// Function call
checkXOR(arr, N);
</script>
Producción:
0 1 2 2 3 4 0 1 4 2 3 4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sudhanshugupta2019a y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA