Dadas dos arrays arr1[] de tamaño M y arr2[] de tamaño N , la tarea es encontrar la suma de OR bit a bit de cada elemento de arr1[] con cada elemento de la array arr2[] .
Ejemplos:
Entrada: arr1[] = {1, 2, 3}, arr2[] = {1, 2, 3}, M = 3, N = 3
Salida: 7 8 9
Explicación:
Para arr[0]: Sum = arr1[ 0]|arr2[0] + arr1[0]|arr2[1] + arr1[0]|arr2[2], Suma = 1|1 + 1|2 + 1|3 = 7
Para arr[1], Suma = arr1[1]|arr2[0] + arr1[1]|arr2[1] + arr1[1]|arr2[2], Sum= 2|1 + 2|2 + 2|3 = 8
Para arr[2 ], Suma = arr1[2]|arr2[0] + arr1[2]|arr2[1] + arr1[2]|arr2[2], Suma = 3|1 + 3|2 + 3|3 = 9Entrada: arr1[] = {2, 4, 8, 16}, arr2[] = {2, 4, 8, 16}, M = 4, N = 4
Salida: 36 42 54 78
Enfoque ingenuo: el enfoque más simple para resolver este problema para atravesar la array arr1[] y para cada elemento de la array en la array arr[] , calcular Bitwise OR de cada elemento en la array arr2[] .
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la manipulación de bits para resolver el problema anterior.
- De acuerdo con la propiedad Bitwise OR , mientras se realiza la operación, el i -ésimo bit se establecerá solo cuando cualquiera de los dos números tenga un bit establecido en la i -ésima posición, donde 0 ≤ i <32 .
- Por lo tanto, para un número en arr1[] , si el i -ésimo bit no es un bit establecido , entonces el i -ésimo lugar contribuirá con una suma de K * 2 i , donde K es el número total en arr2[] que tiene el bit establecido en la i -ésima posición.
- De lo contrario, si el número tiene un bit establecido en el i -ésimo lugar, contribuirá con una suma de N * 2 i .
Siga los pasos a continuación para resolver el problema:
- Inicialice una array de enteros, por ejemplo, frecuencia[] , para almacenar el recuento de números en arr2[] con un bit establecido en la i -ésima posición (0 ≤ i <32).
- Recorra la array arr2[] y represente cada elemento de la array en su forma binaria e incremente el conteo en la array de frecuencia[] en uno en las posiciones que tienen un bit establecido en las representaciones binarias .
- Recorre la array arr1[] .
- Inicialice una variable entera, digamos bitwise_OR_sum con 0 .
- Traverse en el rango [0, 31] usando la variable j .
- Si el j -ésimo bit se establece en la representación binaria de arr2[i] , entonces incremente bitwise_OR_sum en N * 2 j . De lo contrario, incremente por frecuencia[j] * 2 j
- Imprime la suma obtenida bitwise_OR_sum .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to compute sum of Bitwise OR
// of each element in arr1[] with all
// elements of the array arr2[]
void Bitwise_OR_sum_i(int arr1[], int arr2[],
int M, int N)
{
// Declaring an array of
// size 32 to store the
// count of each bit
int frequency[32] = { 0 };
// Traverse the array arr1[]
for (int i = 0; i < N; i++) {
// Current bit position
int bit_position = 0;
int num = arr1[i];
// While num exceeds 0
while (num) {
// Checks if i-th bit
// is set or not
if (num & 1) {
// Increment the count at
// bit_position by one
frequency[bit_position] += 1;
}
// Increment bit_position
bit_position += 1;
// Right shift the num by one
num >>= 1;
}
}
// Traverse in the arr2[]
for (int i = 0; i < M; i++) {
int num = arr2[i];
// Store the ith bit value
int value_at_that_bit = 1;
// Total required sum
int bitwise_OR_sum = 0;
// Traverse in the range [0, 31]
for (int bit_position = 0;
bit_position < 32;
bit_position++) {
// Check if current bit is set
if (num & 1) {
// Increment the Bitwise
// sum by N*(2^i)
bitwise_OR_sum
+= N * value_at_that_bit;
}
else {
bitwise_OR_sum
+= frequency[bit_position]
* value_at_that_bit;
}
// Right shift num by one
num >>= 1;
// Left shift valee_at_that_bit by one
value_at_that_bit <<= 1;
}
// Print the sum obtained for ith
// number in arr1[]
cout << bitwise_OR_sum << ' ';
}
return;
}
// Driver Code
int main()
{
// Given arr1[]
int arr1[] = { 1, 2, 3 };
// Given arr2[]
int arr2[] = { 1, 2, 3 };
// Size of arr1[]
int N = sizeof(arr1) / sizeof(arr1[0]);
// Size of arr2[]
int M = sizeof(arr2) / sizeof(arr2[0]);
// Function Call
Bitwise_OR_sum_i(arr1, arr2, M, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to compute sum of Bitwise OR
// of each element in arr1[] with all
// elements of the array arr2[]
static void Bitwise_OR_sum_i(int arr1[], int arr2[],
int M, int N)
{
// Declaring an array of
// size 32 to store the
// count of each bit
int frequency[] = new int[32];
Arrays.fill(frequency, 0);
// Traverse the array arr1[]
for(int i = 0; i < N; i++)
{
// Current bit position
int bit_position = 0;
int num = arr1[i];
// While num exceeds 0
while (num != 0)
{
// Checks if i-th bit
// is set or not
if ((num & 1) != 0)
{
// Increment the count at
// bit_position by one
frequency[bit_position] += 1;
}
// Increment bit_position
bit_position += 1;
// Right shift the num by one
num >>= 1;
}
}
// Traverse in the arr2[]
for(int i = 0; i < M; i++)
{
int num = arr2[i];
// Store the ith bit value
int value_at_that_bit = 1;
// Total required sum
int bitwise_OR_sum = 0;
// Traverse in the range [0, 31]
for(int bit_position = 0;
bit_position < 32;
bit_position++)
{
// Check if current bit is set
if ((num & 1) != 0)
{
// Increment the Bitwise
// sum by N*(2^i)
bitwise_OR_sum += N * value_at_that_bit;
}
else
{
bitwise_OR_sum += frequency[bit_position] *
value_at_that_bit;
}
// Right shift num by one
num >>= 1;
// Left shift valee_at_that_bit by one
value_at_that_bit <<= 1;
}
// Print the sum obtained for ith
// number in arr1[]
System.out.print(bitwise_OR_sum + " ");
}
return;
}
// Driver code
public static void main(String[] args)
{
// Given arr1[]
int arr1[] = { 1, 2, 3 };
// Given arr2[]
int arr2[] = { 1, 2, 3 };
// Size of arr1[]
int N = arr1.length;
// Size of arr2[]
int M = arr2.length;
// Function Call
Bitwise_OR_sum_i(arr1, arr2, M, N);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach # Function to compute sum of Bitwise OR # of each element in arr1[] with all # elements of the array arr2[] def Bitwise_OR_sum_i(arr1, arr2, M, N): # Declaring an array of # size 32 to store the # count of each bit frequency = [0] * 32 # Traverse the array arr1[] for i in range(N): # Current bit position bit_position = 0 num = arr1[i] # While num exceeds 0 while (num): # Checks if i-th bit # is set or not if (num & 1 != 0): # Increment the count at # bit_position by one frequency[bit_position] += 1 # Increment bit_position bit_position += 1 # Right shift the num by one num >>= 1 # Traverse in the arr2[] for i in range(M): num = arr2[i] # Store the ith bit value value_at_that_bit = 1 # Total required sum bitwise_OR_sum = 0 # Traverse in the range [0, 31] for bit_position in range(32): # Check if current bit is set if (num & 1 != 0): # Increment the Bitwise # sum by N*(2^i) bitwise_OR_sum += N * value_at_that_bit else: bitwise_OR_sum += (frequency[bit_position] * value_at_that_bit) # Right shift num by one num >>= 1 # Left shift valee_at_that_bit by one value_at_that_bit <<= 1 # Print the sum obtained for ith # number in arr1[] print(bitwise_OR_sum, end = " ") return # Driver Code # Given arr1[] arr1 = [ 1, 2, 3 ] # Given arr2[] arr2 = [ 1, 2, 3 ] # Size of arr1[] N = len(arr1) # Size of arr2[] M = len(arr2) # Function Call Bitwise_OR_sum_i(arr1, arr2, M, N) # This code is contributed by code_hunt
C#
// C# program for the above approach
using System;
class GFG
{
// Function to compute sum of Bitwise OR
// of each element in arr1[] with all
// elements of the array arr2[]
static void Bitwise_OR_sum_i(int[] arr1, int[] arr2,
int M, int N)
{
// Declaring an array of
// size 32 to store the
// count of each bit
int[] frequency = new int[32];
for(int i = 0; i < 32; i++)
{
frequency[i] = 0;
}
// Traverse the array arr1[]
for(int i = 0; i < N; i++)
{
// Current bit position
int bit_position = 0;
int num = arr1[i];
// While num exceeds 0
while (num != 0)
{
// Checks if i-th bit
// is set or not
if ((num & 1) != 0)
{
// Increment the count at
// bit_position by one
frequency[bit_position] += 1;
}
// Increment bit_position
bit_position += 1;
// Right shift the num by one
num >>= 1;
}
}
// Traverse in the arr2[]
for(int i = 0; i < M; i++)
{
int num = arr2[i];
// Store the ith bit value
int value_at_that_bit = 1;
// Total required sum
int bitwise_OR_sum = 0;
// Traverse in the range [0, 31]
for(int bit_position = 0;
bit_position < 32;
bit_position++)
{
// Check if current bit is set
if ((num & 1) != 0)
{
// Increment the Bitwise
// sum by N*(2^i)
bitwise_OR_sum += N * value_at_that_bit;
}
else
{
bitwise_OR_sum += frequency[bit_position] *
value_at_that_bit;
}
// Right shift num by one
num >>= 1;
// Left shift valee_at_that_bit by one
value_at_that_bit <<= 1;
}
// Print the sum obtained for ith
// number in arr1[]
Console.Write(bitwise_OR_sum + " ");
}
return;
}
// Driver Code
public static void Main()
{
// Given arr1[]
int[] arr1 = { 1, 2, 3 };
// Given arr2[]
int[] arr2 = { 1, 2, 3 };
// Size of arr1[]
int N = arr1.Length;
// Size of arr2[]
int M = arr2.Length;
// Function Call
Bitwise_OR_sum_i(arr1, arr2, M, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to compute sum of Bitwise OR
// of each element in arr1[] with all
// elements of the array arr2[]
function Bitwise_OR_sum_i(arr1, arr2, M, N) {
// Declaring an array of
// size 32 to store the
// count of each bit
let frequency = new Array(32).fill(0);
// Traverse the array arr1[]
for (let i = 0; i < N; i++) {
// Current bit position
let bit_position = 0;
let num = arr1[i];
// While num exceeds 0
while (num) {
// Checks if i-th bit
// is set or not
if (num & 1) {
// Increment the count at
// bit_position by one
frequency[bit_position] += 1;
}
// Increment bit_position
bit_position += 1;
// Right shift the num by one
num >>= 1;
}
}
// Traverse in the arr2[]
for (let i = 0; i < M; i++) {
let num = arr2[i];
// Store the ith bit value
let value_at_that_bit = 1;
// Total required sum
let bitwise_OR_sum = 0;
// Traverse in the range [0, 31]
for (let bit_position = 0; bit_position < 32; bit_position++) {
// Check if current bit is set
if (num & 1) {
// Increment the Bitwise
// sum by N*(2^i)
bitwise_OR_sum += N * value_at_that_bit;
}
else {
bitwise_OR_sum += frequency[bit_position] * value_at_that_bit;
}
// Right shift num by one
num >>= 1;
// Left shift valee_at_that_bit by one
value_at_that_bit <<= 1;
}
// Print the sum obtained for ith
// number in arr1[]
document.write(bitwise_OR_sum + ' ');
}
return;
}
// Driver Code
// Given arr1[]
let arr1 = [1, 2, 3];
// Given arr2[]
let arr2 = [1, 2, 3];
// Size of arr1[]
let N = arr1.length;
// Size of arr2[]
let M = arr2.length;
// Function Call
Bitwise_OR_sum_i(arr1, arr2, M, N);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
7 8 9
Complejidad de Tiempo: O(N*32)
Espacio Auxiliar: O(N*32)