Dados dos enteros X (1 ≤ X ≤ 15) e Y . La tarea es encontrar una array de la longitud máxima posible N tal que todos los elementos de la array se encuentren entre 1 y 2 X y no exista ningún subarreglo tal que el valor xor del subarreglo sea 0 o Y . Si existen varias respuestas, imprima cualquiera de ellas. Si no existe tal array, imprima -1
Ejemplos:
Entrada: X = 3, Y = 5
Salida: 1 3 1
(1 ^ 3) = 2
(3 ^ 1) = 2
(1 ^ 3 ^ 1) = 3
Entrada: X = 1, Y = 1
Salida: -1
Enfoque: la idea principal es construir el prefijo-xor de la array requerida y luego construir la array a partir de él. Deje que la array prefix-xor sea pre[] .
Ahora, XOR de cualquiera de los dos pares en la array de prefijos (pre[l] ^ pre[r]) representará el XOR de algún subarreglo de la array original, es decir , arr[l + 1] ^ arr[l + 2] ^ … ^ arr[r] .
Por lo tanto, el problema ahora se reduce a construir una array a partir de los elementos de la array pre[] de modo que ningún par de elementos tenga bit a bit-xor igual a 0 o Y y su longitud debe ser máxima.
Tenga en cuenta que ningún par de números tiene una suma xor bit a bit igual a 0 simplemente significaNo se puede usar el mismo número dos veces .
Si Y ≥ 2 X , ningún par de números menores que 2 X tendrá un bit a bit xor igual a Y , por lo que puede usar todos los números del 1 al 2 X – 1 en cualquier orden. De lo contrario, puede pensar en los números que forman pares, donde cada par consta de 2 números con una suma xor bit a bit igual a Y. De cualquier par, si agrega un número a la array, no puede agregar el otro. Sin embargo, los pares son independientes entre sí: su elección en un par no afecta a ningún otro par. Por lo tanto, puede elegir cualquier número en cualquier par y agregarlos en el orden que desee. Después de construir el arreglo pre[] , puede construir el arreglo original usando: arr[i] = pre[i] ^ pre[i – 1].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum length array
void maxLengthArr(int x, int y)
{
// To store if an element is
// already taken or not
bool ex[(1 << x)];
// To store visited numbers
ex[0] = 1;
vector<int> pre({ 0 });
// For all possible values of pre[]
for (int i = 1; i < (1 << x); i++) {
// If it is already taken
if (ex[i ^ y])
continue;
pre.push_back(i);
ex[i] = 1;
}
// Not possible
if (pre.size() == 1) {
cout << "-1";
return;
}
// Print the array constructing it
// from the prefix-xor array
for (int i = 1; i < pre.size(); i++)
cout << (pre[i] ^ pre[i - 1]) << " ";
}
// Driver code
int main()
{
int X = 3, Y = 5;
maxLengthArr(X, Y);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to find the maximum length array
static void maxLengthArr(int x, int y)
{
// To store if an element is
// already taken or not
boolean[] ex = new boolean[(1 << x)];
// To store visited numbers
ex[0] = true;
Vector<Integer> pre = new Vector<Integer>();
pre.add(0);
// For all possible values of pre[]
for (int i = 1; i < (1 << x); i++)
{
// If it is already taken
if (ex[i ^ y])
continue;
pre.add(i);
ex[i] = true;
}
// Not possible
if (pre.size() == 1)
{
System.out.print("-1");
return;
}
// Print the array constructing it
// from the prefix-xor array
for (int i = 1; i < pre.size(); i++)
System.out.print((pre.get(i) ^
pre.get(i - 1)) + " ");
}
// Driver code
public static void main(String[] args)
{
int X = 3, Y = 5;
maxLengthArr(X, Y);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach
# Function to find the maximum length array
def maxLengthArr(x, y) :
# To store if an element is
# already taken or not
ex = [0] * (1 << x);
# To store visited numbers
ex[0] = 1;
pre = [0];
# For all possible values of pre[]
for i in range(1, (1 << x)) :
# If it is already taken
if (ex[i ^ y]) :
continue;
pre.append(i);
ex[i] = 1;
# Not possible
if (len(pre) == 1) :
print("-1", end = "");
return;
# Print the array constructing it
# from the prefix-xor array
for i in range(1, len(pre)) :
print(pre[i] ^ pre[i - 1], end = " ");
# Driver code
if __name__ == "__main__" :
X = 3; Y = 5;
maxLengthArr(X, Y);
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the maximum length array
static void maxLengthArr(int x, int y)
{
// To store if an element is
// already taken or not
bool[] ex = new bool[(1 << x)];
// To store visited numbers
ex[0] = true;
var pre = new List<int>();
pre.Add(0);
// For all possible values of pre[]
for (int i = 1; i < (1 << x); i++)
{
// If it is already taken
if (ex[i ^ y])
continue;
pre.Add(i);
ex[i] = true;
}
// Not possible
if (pre.Count == 1)
{
Console.Write("-1");
return;
}
// Print the array constructing it
// from the prefix-xor array
for (int i = 1; i < pre.Count; i++)
Console.Write((pre[i] ^ pre[i - 1]) + " ");
}
// Driver code
public static void Main(String[] args)
{
int X = 3, Y = 5;
maxLengthArr(X, Y);
}
}
// This code is contributed by
// sanjeev2552
Javascript
<script>
// Javascript implementation of the approach
// Function to find the maximum length array
function maxLengthArr(x, y)
{
// To store if an element is
// already taken or not
let ex = new Array((1 << x)).fill(0);
// To store visited numbers
ex[0] = 1;
let pre = [];
pre.push(0);
// For all possible values of pre[]
for (let i = 1; i < (1 << x); i++) {
// If it is already taken
if (ex[i ^ y])
continue;
pre.push(i);
ex[i] = 1;
}
// Not possible
if (pre.length == 1) {
document.write("-1");
return;
}
// Print the array constructing it
// from the prefix-xor array
for (let i = 1; i < pre.length; i++)
document.write((pre[i] ^ pre[i - 1]) + " ");
}
// Driver code
let X = 3, Y = 5;
maxLengthArr(X, Y);
</script>
1 3 1
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA