Dado AND bit a bit , OR y XOR de N elementos de una array denotada por a, b, c. La tarea es encontrar los elementos de la array. Si no existe tal array, imprima «-1».
Ejemplos:
Entrada: N = 3, a = 4, b = 6, c = 6.
Salida: {4, 4, 6}
Explicación:
AND bit a bit de array = 4 & 4 & 6 = 4
OR bit a bit de array = 4 | 4 | 6 = 6
Bitwise XOR de array = 4 ^ 4 ^ 6 = 6
Entrada: N = 2, a = 4, b = 6, c = 6.
Salida: -1
Acercarse:
- Para AND bit a bit , si el i -ésimo bit está configurado en a , entonces en la array cada elemento debe tener i -ésimo bit establecido porque incluso si el i -ésimo bit de un elemento es 0 , entonces el bit-ésimo AND de la array dará como resultado que el i -ésimo bit sea 0 .
- En segundo lugar, si el i -ésimo bit no está establecido en a, entonces los valores OR y XOR deben manejarse simultáneamente. Si se establece i -ésimo bit en b , entonces al menos un elemento debe tener i -ésimo bit establecido. Por lo tanto, establezca i -ésimo bit en el único primer elemento de la array.
- Ahora, si el i -ésimo bit se configuró en b , entonces el i -ésimo bit debe verificarse en c . Si ese bit está configurado en c , entonces no hay problema, ya que el i -ésimo bit del primer elemento ya está configurado, por lo que 1 ^ 0 = 1. Si ese bit no está configurado en c, configure el i -ésimo bit del segundo elemento. Ahora, no habrá ningún efecto en b y para c, 1 ^ 1 será 0 .
- Luego, simplemente calcule Bitwise AND, OR y XOR de la array para verificar si es igual o no. Si los resultados no son iguales, entonces la array no es posible; de lo contrario, la array dada es la respuesta.
A continuación se muestra la implementación del enfoque:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the array
void findArray(int n, int a, int b, int c)
{
int arr[n + 1] = {};
// Loop through all bits in number
for (int bit = 30; bit >= 0; bit--) {
// If bit is set in AND
// then set it in every element
// of the array
int set = a & (1 << bit);
if (set) {
for (int i = 0; i < n; i++)
arr[i] |= set;
}
// If bit is not set in AND
else {
// But set in b(OR)
if (b & (1 << bit)) {
// Set bit position
// in first element
arr[0] |= (1 << bit);
// If bit is not set in c
// then set it in second
// element to keep xor as
// zero for bit position
if (!(c & (1 << bit))) {
arr[1] |= (1 << bit);
}
}
}
}
int aa = INT_MAX, bb = 0, cc = 0;
// Calculate AND, OR
// and XOR of array
for (int i = 0; i < n; i++) {
aa &= arr[i];
bb |= arr[i];
cc ^= arr[i];
}
// Check if values are equal or not
if (a == aa && b == bb && c == cc) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// If not, then array
// is not possible
else
cout << "-1";
}
// Driver Code
int main()
{
// Given Bitwise AND, OR, and XOR
int n = 3, a = 4, b = 6, c = 6;
// Function Call
findArray(n, a, b, c);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the array
static void findArray(int n, int a,
int b, int c)
{
int arr[] = new int[n + 1];
// Loop through all bits in number
for(int bit = 30; bit >= 0; bit--)
{
// If bit is set in AND
// then set it in every element
// of the array
int set = a & (1 << bit);
if (set != 0)
{
for(int i = 0; i < n; i++)
arr[i] |= set;
}
// If bit is not set in AND
else
{
// But set in b(OR)
if ((b & (1 << bit)) != 0)
{
// Set bit position
// in first element
arr[0] |= (1 << bit);
// If bit is not set in c
// then set it in second
// element to keep xor as
// zero for bit position
if ((c & (1 << bit)) == 0)
{
arr[1] |= (1 << bit);
}
}
}
}
int aa = Integer.MAX_VALUE, bb = 0, cc = 0;
// Calculate AND, OR
// and XOR of array
for(int i = 0; i < n; i++)
{
aa &= arr[i];
bb |= arr[i];
cc ^= arr[i];
}
// Check if values are equal or not
if (a == aa && b == bb && c == cc)
{
for(int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// If not, then array
// is not possible
else
System.out.println("-1");
}
// Driver code
public static void main(String[] args)
{
// Given Bitwise AND, OR, and XOR
int n = 3, a = 4, b = 6, c = 6;
// Function Call
findArray(n, a, b, c);
}
}
// This code is contributed by Pratima Pandey
Python3
# Python3 program for
# the above approach
import sys
# Function to find the array
def findArray(n, a, b, c):
arr = [0] * (n + 1)
# Loop through all bits in number
for bit in range (30, -1, -1):
# If bit is set in AND
# then set it in every element
# of the array
set = a & (1 << bit)
if (set):
for i in range (n):
arr[i] |= set
# If bit is not set in AND
else :
# But set in b(OR)
if (b & (1 << bit)):
# Set bit position
# in first element
arr[0] |= (1 << bit)
# If bit is not set in c
# then set it in second
# element to keep xor as
# zero for bit position
if (not (c & (1 << bit))):
arr[1] |= (1 << bit)
aa = sys.maxsize
bb = 0
cc = 0
# Calculate AND, OR
# and XOR of array
for i in range (n):
aa &= arr[i]
bb |= arr[i]
cc ^= arr[i]
# Check if values are equal or not
if (a == aa and b == bb and c == cc):
for i in range (n):
print (arr[i], end = " ")
# If not, then array
# is not possible
else:
print ("-1")
# Driver Code
if __name__ =="__main__":
# Given Bitwise AND, OR, and XOR
n = 3
a = 4
b = 6
c = 6
# Function Call
findArray(n, a, b, c)
# This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the array
static void findArray(int n, int a,
int b, int c)
{
int []arr = new int[n + 1];
// Loop through all bits in number
for(int bit = 30; bit >= 0; bit--)
{
// If bit is set in AND
// then set it in every element
// of the array
int set = a & (1 << bit);
if (set != 0)
{
for(int i = 0; i < n; i++)
arr[i] |= set;
}
// If bit is not set in AND
else
{
// But set in b(OR)
if ((b & (1 << bit)) != 0)
{
// Set bit position
// in first element
arr[0] |= (1 << bit);
// If bit is not set in c
// then set it in second
// element to keep xor as
// zero for bit position
if ((c & (1 << bit)) == 0)
{
arr[1] |= (1 << bit);
}
}
}
}
int aa = int.MaxValue, bb = 0, cc = 0;
// Calculate AND, OR
// and XOR of array
for(int i = 0; i < n; i++)
{
aa &= arr[i];
bb |= arr[i];
cc ^= arr[i];
}
// Check if values are equal or not
if (a == aa && b == bb && c == cc)
{
for(int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// If not, then array
// is not possible
else
Console.WriteLine("-1");
}
// Driver code
public static void Main(String[] args)
{
// Given Bitwise AND, OR, and XOR
int n = 3, a = 4, b = 6, c = 6;
// Function Call
findArray(n, a, b, c);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to find the array
function findArray(n, a, b, c) {
let arr = new Array(n + 1);
// Loop through all bits in number
for (let bit = 30; bit >= 0; bit--) {
// If bit is set in AND
// then set it in every element
// of the array
let set = a & (1 << bit);
if (set) {
for (let i = 0; i < n; i++)
arr[i] |= set;
}
// If bit is not set in AND
else {
// But set in b(OR)
if (b & (1 << bit)) {
// Set bit position
// in first element
arr[0] |= (1 << bit);
// If bit is not set in c
// then set it in second
// element to keep xor as
// zero for bit position
if (!(c & (1 << bit))) {
arr[1] |= (1 << bit);
}
}
}
}
let aa = Number.MAX_SAFE_INTEGER, bb = 0, cc = 0;
// Calculate AND, OR
// and XOR of array
for (let i = 0; i < n; i++) {
aa &= arr[i];
bb |= arr[i];
cc ^= arr[i];
}
// Check if values are equal or not
if (a == aa && b == bb && c == cc) {
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// If not, then array
// is not possible
else
document.write("-1");
}
// Driver Code
// Given Bitwise AND, OR, and XOR
let n = 3, a = 4, b = 6, c = 6;
// Function Call
findArray(n, a, b, c);
// This code is contributed by gfgking
</script>
Producción:
6 4 4
Complejidad de tiempo: O(31*N)
Publicación traducida automáticamente
Artículo escrito por sarthak_eddy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA