Dados dos enteros N e Y , la tarea es generar una secuencia de N enteros no negativos distintos cuyo bit a bit XOR de todos los elementos de esta secuencia generada sea igual a Y , es decir , A 1 ^ A 2 ^ A 3 ^ ….. ^ A N = Y donde ^ denota XOR bit a bit. si tal secuencia no es posible, imprima -1 .
Ejemplos:
Entrada: N = 4, Y = 3
Salida: 1 131072 131074 0
(1 ^ 131072 ^ 131074 ^ 0) = 3 y los cuatro elementos son distintos.
Entrada: N = 10, Y = 6
Salida: 1 2 3 4 5 6 7 131072 131078 0
Enfoque: Este es un problema constructivo y puede contener múltiples soluciones. Siga los pasos a continuación para generar la secuencia requerida:
- Tome los primeros N – 3 elementos como parte de la secuencia, es decir , 1, 2, 3, 4, …, (N – 3)
- Sea x el XOR de los elementos elegidos y sea num un número entero que aún no ha sido elegido. Ahora hay dos casos:
- Si x = y entonces podemos sumar num , num * 2 y (num ^ (num * 2)) a los 3 últimos números restantes porque num ^ (num * 2) ^ (num ^ (num * 2)) = 0 y x ^ 0 = x
- Si x != y entonces podemos sumar 0 , num y (num ^ x ^ y) porque 0 ^ num ^ (num ^ x ^ y) = x ^ y y x ^ x ^ y = y
Nota: La secuencia no es posible cuando N = 2 e Y = 0 porque esta condición solo puede ser satisfecha por dos números iguales, lo cual no está permitido.
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 and print
// the required sequence
void Findseq(int n, int x)
{
const int pw1 = (1 << 17);
const int pw2 = (1 << 18);
// Base case
if (n == 1)
cout << x << endl;
// Not allowed case
else if (n == 2 && x == 0)
cout << "-1" << endl;
else if (n == 2)
cout << x << " "
<< "0" << endl;
else {
int i;
int ans = 0;
// XOR of first N - 3 elements
for (i = 1; i <= n - 3; i++) {
cout << i << " ";
ans = ans ^ i;
}
// Case 1: Add three integers whose XOR is 0
if (ans == x)
cout << pw1 + pw2 << " "
<< pw1 << " " << pw2 << endl;
// Case 2: Add three integers
// whose XOR is equal to ans
else
cout << pw1 << " " << ((pw1 ^ x) ^ ans)
<< " 0 " << endl;
}
}
// Driver code
int main()
{
int n = 4, x = 3;
Findseq(n, x);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG {
// Function to find and print
// the required sequence
static void Findseq(int n, int x)
{
int pw1 = 1 << 17;
int pw2 = (1 << 18);
// Base case
if (n == 1) {
System.out.println(x);
}
// Not allowed case
else if (n == 2 && x == 0) {
System.out.println("-1");
}
else if (n == 2) {
System.out.println(x + " "
+ "");
}
else {
int i;
int ans = 0;
// XOR of first N - 3 elements
for (i = 1; i <= n - 3; i++) {
System.out.print(i + " ");
ans = ans ^ i;
}
// Case 1: Add three integers whose XOR is 0
if (ans == x) {
System.out.println(pw1 + pw2 + " " + pw1 + " " + pw2);
}
// Case 2: Add three integers
// whose XOR is equal to ans
else {
System.out.println(pw1 + " " + ((pw1 ^ x) ^ ans)
+ " 0 ");
}
}
}
// Driver code
public static void main(String[] args)
{
int n = 4, x = 3;
Findseq(n, x);
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation of the approach
# Function to find and print
# the required sequence
def Findseq(n, x) :
pw1 = (1 << 17);
pw2 = (1 << 18);
# Base case
if (n == 1) :
print(x);
# Not allowed case
elif (n == 2 and x == 0) :
print("-1");
elif (n == 2) :
print(x, " ", "0");
else :
ans = 0;
# XOR of first N - 3 elements
for i in range(1, n - 2) :
print(i, end = " ");
ans = ans ^ i;
# Case 1: Add three integers whose XOR is 0
if (ans == x) :
print(pw1 + pw2, " ", pw1, " ", pw2);
# Case 2: Add three integers
# whose XOR is equal to ans
else :
print(pw1, " ", ((pw1 ^ x) ^ ans), " 0 ");
# Driver code
if __name__ == "__main__" :
n = 4; x = 3;
Findseq(n, x);
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find and print
// the required sequence
static void Findseq(int n, int x)
{
int pw1 = 1 << 17;
int pw2 = (1 << 18);
// Base case
if (n == 1)
{
Console.WriteLine(x);
}
// Not allowed case
else if (n == 2 && x == 0)
{
Console.WriteLine("-1");
}
else if (n == 2)
{
Console.WriteLine(x + " "
+ "");
}
else
{
int i;
int ans = 0;
// XOR of first N - 3 elements
for (i = 1; i <= n - 3; i++)
{
Console.Write(i + " ");
ans = ans ^ i;
}
// Case 1: Add three integers whose XOR is 0
if (ans == x)
{
Console.WriteLine(pw1 + pw2 + " " + pw1 + " " + pw2);
}
// Case 2: Add three integers
// whose XOR is equal to ans
else
{
Console.WriteLine(pw1 + " " + ((pw1 ^ x) ^ ans)
+ " 0 ");
}
}
}
// Driver code
public static void Main()
{
int n = 4, x = 3;
Findseq(n, x);
}
}
// This code contributed by anuj_67..
PHP
<?php
// PHP implementation of the approach
// Function to find and print
// the required sequence
function Findseq($n, $x)
{
$pw1 = (1 << 17);
$pw2 = (1 << 18);
// Base case
if ($n == 1)
echo $x ,"\n";
// Not allowed case
else if ($n == 2 && $x == 0)
echo "-1" ,"\n";
else if ($n == 2)
echo $x ," ",
"0","\n";
else
{
$i;
$ans = 0;
// XOR of first N - 3 elements
for ($i = 1; $i <= $n - 3; $i++)
{
echo $i , " ";
$ans = $ans ^ $i;
}
// Case 1: Add three integers whose XOR is 0
if ($ans == $x)
echo ($pw1 + $pw2) , " ",
$pw1 ," " , $pw2,"\n";
// Case 2: Add three integers
// whose XOR is equal to ans
else
echo $pw1 , " " ,(($pw1 ^ $x) ^ $ans),
" 0 " ,"\n";
}
}
// Driver code
$n = 4;
$x = 3;
Findseq($n, $x);
// This code is contributed BY @Tushil..
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to find and print
// the required sequence
function Findseq(n, x)
{
let pw1 = (1 << 17);
let pw2 = (1 << 18);
// Base case
if (n == 1)
document.write(x + "<br>");
// Not allowed case
else if (n == 2 && x == 0)
document.write("-1<br>");
else if (n == 2)
document.write(x + " "
+ "0" + "<br>");
else {
let i;
let ans = 0;
// XOR of first N - 3 elements
for (i = 1; i <= n - 3; i++) {
document.write(i + " ");
ans = ans ^ i;
}
// Case 1: Add three integers whose XOR is 0
if (ans == x)
document.write((pw1 + pw2) + " "
+ pw1 + " " <+ pw2 + "<br>");
// Case 2: Add three integers
// whose XOR is equal to ans
else
document.write(pw1 + " " + ((pw1 ^ x) ^ ans)
+ " 0 " + "<br>");
}
}
// Driver code
let n = 4, x = 3;
Findseq(n, x)
</script>
Producción:
1 131072 131074 0
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por sharadgoyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA