Construya la array utilizando AND, OR y XOR bit a bit dados

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:  

  1. 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 .
  2. 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.
  3. 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 .
  4. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *