Dados dos enteros positivos N y X , la tarea es construir N enteros positivos que tengan un XOR bit a bit de todos estos enteros igual a K .
Ejemplos:
Entrada: N = 4, K = 6
Salida: 1 0 2 5
Explicación: Bitwise XOR los enteros {1, 0, 2, 5} = 1 XOR 0 XOR 2 XOR 5 = 6(= K).Entrada: N = 1, K = 1
Salida: 1
Enfoque: La idea para resolver este problema es incluir los primeros (N – 3) números naturales y calcular su XOR bit a bit y seleccionar los 3 enteros restantes en función de los valores XOR calculados. Siga los pasos a continuación para resolver el problema:
- Si N = 1: Imprime el propio entero K.
- Si N = 2: Imprima K y 0 como la salida requerida.
- De lo contrario, considere los primeros (N – 3) números naturales.
- Ahora, calcule Bitwise XOR de (N – 3) elementos y guárdelo en una variable, digamos val . Los tres elementos restantes se pueden seleccionar en función de las siguientes condiciones:
- Caso 1: Si val es igual a K , realice los siguientes pasos:
- En este caso, el XOR bit a bit de los tres elementos restantes debe ser igual a cero para que el XOR bit a bit de todos los enteros sea igual a K .
- Por lo tanto, los tres elementos restantes deben ser P, Q, P XOR Q , lo que hace que su Bitwise XOR sea igual a 0 . Pero PXOR Q debe ser mayor que N-2 (es decir, P ) para que todos los números permanezcan distintos . (En caso de que se pregunte si P XOR Q tampoco debería ser igual a Q , bueno, esto no es posible ya que el valor de P nunca será cero.
- Caso (i): P XOR Q ya es mayor que P :
- Los tres elementos restantes serán P, Q, P XOR Q.
- Caso (ii): P XOR Q no es mayor que P :
- Aquí, usaremos el bucle while con la condición P XOR Q <= P con un incremento de Q de 1. Después de la terminación del bucle, los tres elementos restantes serán P, Q, P XOR Q.
- Caso 2: Si val no es igual a K , realice los siguientes pasos:
- En este caso, Bitwise XOR de los tres elementos restantes junto con Bitwise XOR de los primeros (N – 3) elementos debe ser igual a K .
- Al considerar que los últimos 3 elementos son iguales a 0, P, P XOR K XOR val , Bitwise XOR de estos tres elementos es igual a K XOR val . De nuevo, P XOR K XOR val debe ser mayor que N-2 para que todos los N números sean distintos .
- Caso (i): P XOR K XOR val ya es mayor que N-2 :
- Los tres elementos restantes serán 0 , P , P XOR K XOR val .
- Caso (ii): P XOR K XOR val no es mayor que N-2 :
- Aquí, usaremos el bucle while con la condición P XOR K XOR val <= N-2 con un incremento de P en 1. Después de la terminación del bucle, los tres elementos restantes serán 0, P, P XOR K XOR val.
- Caso 1: Si val es igual a K , realice los siguientes pasos:
- Elección de P y Q: Para ambos casos, el valor de P y Q requiere ser distinto de los primeros (N – 3) elementos. Por lo tanto, considere que P y Q son (N – 2) y (N – 1) .
- En caso de que se esté preguntando si los bucles pueden estar atascados durante demasiado tiempo, no es cierto. Por lo general, obtendrá el número en el rango de 100 iteraciones. Entonces, en promedio, la complejidad temporal de ambos bucles while mencionados en los casos 1 y 2 es casi constante.
A continuación se muestra la implementación de la solución anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find N integers
// having Bitwise XOR equal to K
void findArray(int N, int K)
{
// Base Cases
if (N == 1)
{
cout << " " << K;
return;
}
if (N == 2)
{
cout << 0 << " " << K;
return;
}
// Assign values to P and Q
int P = N - 2;
int Q = N - 1;
// Stores Bitwise XOR of the
// first (N - 3) elements
int VAL = 0;
// Print the first N - 3 elements
for(int i = 1; i <= (N - 3); i++)
{
cout << " " << i;
// Calculate Bitwise XOR of
// first (N - 3) elements
VAL ^= i;
}
if (VAL == K)
{ // checking whether P ^ Q is greater than P or not.
while( (P ^ Q) <= P)
{ Q++;
}
cout << " " << P << " " << Q
<< " " << (P ^ Q);
}
else
{ // checking whether P ^ K ^ VAL is greater than N-2 or not.
while( (P ^ K ^ VAL) <= N-3)
{ P++;
}
cout << " " << 0 << " " << P
<< " " << (P ^ K ^ VAL);
}
}
// Driver Code
int main()
{
int N = 4, X = 6;
// Function Call
findArray(N, X);
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C program for the above approach
#include <stdio.h>
// Function to find N integers
// having Bitwise XOR equal to K
void findArray(int N, int K)
{
// Base Cases
if (N == 1) {
printf("%d", K);
return;
}
if (N == 2) {
printf("%d %d", 0, K);
return;
}
// Assign values to P and Q
int P = N - 2;
int Q = N - 1;
// Stores Bitwise XOR of the
// first (N - 3) elements
int VAL = 0;
// Print the first N - 3 elements
for (int i = 1; i <= (N - 3); i++) {
printf("%d ", i);
// Calculate Bitwise XOR of
// first (N - 3) elements
VAL ^= i;
}
if (VAL == K) {
// checking whether P ^ Q is greater than P or not.
while( (P ^ Q) <= P)
{ Q++;
}
printf("%d %d %d", P, Q, P ^ Q);
}
else {
// checking whether P ^ K ^ VAL is greater than N-2 or not.
while( (P ^ K ^ VAL) <= N-2)
{ P++;
}
printf("%d %d %d", 0,
P, P ^ K ^ VAL);
}
}
// Driver Code
int main()
{
int N = 4, X = 6;
// Function Call
findArray(N, X);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find N integers
// having Bitwise XOR equal to K
static void findArray(int N, int K)
{
// Base Cases
if (N == 1)
{
System.out.print(K + " ");
return;
}
if (N == 2)
{
System.out.print(0 + " " + K);
return;
}
// Assign values to P and Q
int P = N - 2;
int Q = N - 1;
// Stores Bitwise XOR of the
// first (N - 3) elements
int VAL = 0;
// Print the first N - 3 elements
for(int i = 1; i <= (N - 3); i++)
{
System.out.print(i + " ");
// Calculate Bitwise XOR of
// first (N - 3) elements
VAL ^= i;
}
if (VAL == K)
{ // checking whether P ^ Q is greater than P or not.
while( (P ^ Q) <= P)
{ Q++;
}
System.out.print(P + " " +
Q + " " + (P ^ Q));
}
else
{ // checking whether P ^ K ^ VAL is greater than N-2 or not.
while( (P ^ K ^ VAL) <= N-2)
{ P++;
}
System.out.print(0 + " " +
P + " " +
(P ^ K ^ VAL));
}
}
// Driver Code
public static void main(String[] args)
{
int N = 4, X = 6;
// Function Call
findArray(N, X);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach
# Function to find N integers
# having Bitwise XOR equal to K
def findArray(N, K):
# Base Cases
if (N == 1):
print(K, end=" ")
return
if (N == 2):
print("0", end=" ")
print(K, end=" ")
return
# Assign values to P and Q
P = N - 2
Q = N - 1
# Stores Bitwise XOR of the
# first (N - 3) elements
VAL = 0
# Print the first N - 3 elements
for i in range(1, N - 2):
print(i, end=" ")
# Calculate Bitwise XOR of
# first (N - 3) elements
VAL ^= i
if (VAL == K):
# checking whether P ^ Q is greater than P or not.
while ((P ^ Q) <= P):
Q = Q + 1
print(P, end=" ")
print(Q, end=" ")
print(P ^ Q, end=" ")
else:
# checking whether P ^ K ^ VAL is greater than N-2 or not.
while ((P ^ K ^ VAL) <= N - 2):
P = P + 1
print("0", end=" ")
print(P, end=" ")
print(P ^ K ^ VAL, end=" ")
# Driver Code
N = 4
X = 6
# Function Call
findArray(N, X)
# This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG{
// Function to find N integers
// having Bitwise XOR equal to K
static void findArray(int N, int K)
{
// Base Cases
if (N == 1) {
Console.Write(K + " ");
return;
}
if (N == 2) {
Console.Write(0 + " " + K);
return;
}
// Assign values to P and Q
int P = N - 2;
int Q = N - 1;
// Stores Bitwise XOR of the
// first (N - 3) elements
int VAL = 0;
// Print the first N - 3 elements
for (int i = 1; i <= (N - 3); i++) {
Console.Write(i + " ");
// Calculate Bitwise XOR of
// first (N - 3) elements
VAL ^= i;
}
if (VAL == K) {
// checking whether P ^ Q is greater than P or not.
while( (P ^ Q) <= P)
{ Q++;
}
Console.Write(P + " " + Q + " " + (P ^ Q));
}
else {
// checking whether P ^ K ^ VAL is greater than N-2 or not.
while( (P ^ K ^ VAL) <= N-2)
{ P++;
}
Console.Write(0 + " " + P + " " + (P ^ K ^ VAL));
}
}
// Driver Code
public static void Main()
{
int N = 4, X = 6;
// Function Call
findArray(N, X);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// Javascript program for the above approach
// Function to find N integers
// having Bitwise XOR equal to K
function findArray(N, K)
{
// Base Cases
if (N == 1)
{
document.write(K + " ");
return;
}
if (N == 2)
{
document.write(0 + " " + K);
return;
}
// Assign values to P and Q
let P = N - 2;
let Q = N - 1;
// Stores Bitwise XOR of the
// first (N - 3) elements
let VAL = 0;
// Print the first N - 3 elements
for(let i = 1; i <= (N - 3); i++)
{
document.write(i + " ");
// Calculate Bitwise XOR of
// first (N - 3) elements
VAL ^= i;
}
if (VAL == K)
{ // checking whether P ^ Q is greater than P or not.
while( (P ^ Q) <= P)
{ Q++;
}
document.write(P + " " +
Q + " " + (P ^ Q));
}
else
{ // checking whether P ^ K ^ VAL is greater than N-2 or not.
while( (P ^ K ^ VAL) <= N-2)
{ P++;
}
document.write(0 + " " +
P + " " +
(P ^ K ^ VAL));
}
}
// Driver Code
let N = 4, X = 6;
// Function Call
findArray(N, X);
</script>
Producción:
1 0 2 5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)