Genere una array que tenga la suma de Bitwise O de los mismos elementos indexados con una array dada igual a K

Dada una array arr[] que consiste en N enteros y un entero K, la tarea es imprimir una array generada de tal manera que la suma de Bitwise OR de los mismos elementos indexados de la array generada con la array dada sea igual a K. Si es no es posible generar una array de este tipo, luego imprima «-1».

Ejemplos:

Entrada: arr[] = {6, 6, 6, 6}, K = 34
Salida: 15 7 6 6
Explicación: 
XOR bit a bit de elementos del mismo índice de las arrays {6, 6, 6, 6} y {15, 7, 6, 6} son:
6|15 = 15
6|7 = 7
6|6 = 6
6|6 = 6
Suma de OR bit a bit = 15 + 7 + 6 + 6 = 34 (= K)

Entrada: arr[] = {1, 2, 3, 4}, K = 32
Salida: 23 2 3 4

Acercarse:

• Primero, calcule la suma de la array arr[] y guárdela en una variable, digamos sum.
• Inicialice un vector<int> , digamos B, para almacenar la array resultante.
• Actualice el valor de K como K = K – suma.
• Si K es menor que 0 , imprima -1.
• Recorra la array arr[] y realice las siguientes operaciones:
  • Inicialice una variable, digamos curr, para almacenar los elementos de la array resultante.
  • Atraviesa los bits del elemento de array actual.
  • Compruebe si el bit actual está establecido o no y 2 ^j ≤ K o no. Si se determina que es cierto, actualice curr como curr = curr | (1<<j) y K = K – (1 << j).
  • Ahora, empuje el curr en el vector B.
• Imprime el vector B si K es 0 . De lo contrario, imprima -1.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the resultant array
void constructArr(int A[], int N, int K)
{
    // Stores the sum of the array
    int sum = 0;
 
    // Calculate sum of the array
    for (int i = 0; i < N; i++) {
        sum += A[i];
    }
 
    // If sum > K
    if (sum > K) {
 
        // Not possible to
        // construct the array
        cout << -1 << "\n";
        return;
    }
 
    // Update K
    K -= sum;
 
    // Stores the resultant array
    vector<int> B;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Stores the current element
        int curr = A[i];
 
        for (int j = 32; j >= 0 and K; j--) {
 
            // If jth bit is not set and
            // value of 2^j is less than K
            if ((curr & (1LL << j)) == 0
                and (1LL << j) <= K) {
 
                // Update curr
                curr |= (1LL << j);
 
                // Update K
                K -= (1LL << j);
            }
        }
 
        // Push curr into B
        B.push_back(curr);
    }
 
    // If K is greater than 0
    if (!K) {
 
        // Print the vector B
        for (auto it : B) {
            cout << it << " ";
        }
        cout << "\n";
    }
 
    // Otherwise
    else {
        cout << "-1"
             << "\n";
    }
}
 
// Driver Code
int main()
{
    // Input
    int arr[] = { 1, 2, 3, 4 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given input
    int K = 32;
 
    // Function call to print
    // the required array
    constructArr(arr, N, K);
}

# Python 3 program for the above approach
 
# Function to print the resultant array
def constructArr(A, N, K):
   
    # Stores the sum of the array
    sum = 0
 
    # Calculate sum of the array
    for i in range(N):
        sum += A[i]
 
    # If sum > K
    if (sum > K):
       
        # Not possible to
        # construct the array
        print(-1)
        return
 
    # Update K
    K -= sum
 
    # Stores the resultant array
    B = []
 
    # Traverse the array
    for i in range(N):
       
        # Stores the current element
        curr = A[i]
        j = 32
 
        while(j >= 0 and K>0):
           
            # If jth bit is not set and
            # value of 2^j is less than K
            if ((curr & (1 << j)) == 0 and (1 << j) <= K):
               
                # Update curr
                curr |= (1 << j)
 
                # Update K
                K -= (1 << j)
            j -= 1
 
        # Push curr into B
        B.append(curr)
 
    # If K is greater than 0
    if (K == 0):
        # Print the vector B
        for it in B:
            print(it,end=" ")
        print("\n",end = "")
 
    # Otherwise
    else:
        print("-1")
 
# Driver Code
if __name__ == '__main__':
    # Input
    arr = [1, 2, 3, 4]
     
    # Size of the array
    N = len(arr)
     
    # Given input
    K = 32
     
    # Function call to print
    # the required array
    constructArr(arr, N, K)
 
# This code is contributed by ipg2016107.

23 2 3 4

Complejidad temporal: O(N)
Espacio auxiliar: O(N)