Dado un arreglo arr[] que consta de enteros no negativos, la tarea para cada elemento del arreglo arr[i] es imprimir la suma de Bitwise OR de todos los pares (arr[i], arr[j]) ( 0 ≤ j ≤ N ).
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: 12 14 16 22
Explicación:
Para i = 0 la suma requerida será (1 | 1) + (1 | 2) + (1 | 3) + (1 | 4) = 12
Para i = 1 la suma requerida será (2 | 1) + (2 | 2) + (2 | 3) + (2 | 4) = 14
Para i = 2 la suma requerida será (3 | 1) + (3 | 2) + (3 | 3) + (3 | 4) = 16
Para i = 3 la suma requerida será (4 | 1) + (4 | 2) + (4 | 3 ) + (4 | 4) = 22Entrada: arr[] = {3, 2, 5, 4, 8}
Salida: 31 28 37 34 54
Enfoque ingenuo: el enfoque más simple para cada elemento de array arr[i] es recorrer la array y calcular la suma de Bitwise O de todos los posibles (arr[i], arr[j]) e imprimir la suma obtenida .
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 print required sum for
// every valid index i
void printORSumforEachElement(int arr[], int N)
{
for (int i = 0; i < N; i++) {
// Store the required sum
// for current array element
int req_sum = 0;
// Generate all possible pairs (arr[i], arr[j])
for (int j = 0; j < N; j++) {
// Update the value of req_sum
req_sum += (arr[i] | arr[j]);
}
// Print the required sum
cout << req_sum << " ";
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 2, 3, 4 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
printORSumforEachElement(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to print required sum for
// every valid index i
static void printORSumforEachElement(int arr[], int N)
{
for (int i = 0; i < N; i++)
{
// Store the required sum
// for current array element
int req_sum = 0;
// Generate all possible pairs (arr[i], arr[j])
for (int j = 0; j < N; j++)
{
// Update the value of req_sum
req_sum += (arr[i] | arr[j]);
}
// Print the required sum
System.out.print(req_sum+ " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 1, 2, 3, 4 };
// Size of the array
int N = arr.length;
// Function Call
printORSumforEachElement(arr, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to print required sum for # every valid index i def printORSumforEachElement(arr, N): for i in range(0, N): # Store the required sum # for current array element req_sum = 0 # Generate all possible pairs(arr[i],arr[j]) for j in range(0, N): # Update the value of req_sum req_sum += (arr[i] | arr[j]) # Print required sum print(req_sum, end = " ") # Driver code # Given array arr = [ 1, 2, 3, 4 ] # Size of array N = len(arr) # Function call printORSumforEachElement(arr, N) # This code is contributed by Virusbuddah
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to print required sum for
// every valid index i
static void printORSumforEachElement(int []arr, int N)
{
for (int i = 0; i < N; i++)
{
// Store the required sum
// for current array element
int req_sum = 0;
// Generate all possible pairs (arr[i], arr[j])
for (int j = 0; j < N; j++)
{
// Update the value of req_sum
req_sum += (arr[i] | arr[j]);
}
// Print the required sum
Console.Write(req_sum+ " ");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 1, 2, 3, 4 };
// Size of the array
int N = arr.Length;
// Function Call
printORSumforEachElement(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program of the above approach
// Function to print required sum for
// every valid index i
function prletORSumforEachElement(arr, N)
{
for(let i = 0; i < N; i++)
{
// Store the required sum
// for current array element
let req_sum = 0;
// Generate all possible pairs
// (arr[i], arr[j])
for(let j = 0; j < N; j++)
{
// Update the value of req_sum
req_sum += (arr[i] | arr[j]);
}
// Print the required sum
document.write(req_sum + " ");
}
}
// Driver Code
// Given array
let arr = [ 1, 2, 3, 4 ];
// Size of the array
let N = arr.length;
// Function Call
prletORSumforEachElement(arr, N);
// This code is contributed by avijitmondal1998
</script>
Producción:
12 14 16 22
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea óptima es usar la manipulación de bits asumiendo que los números enteros se representan usando 32 bits . Siga los pasos a continuación para resolver el problema:
- Considere cada bit k-ésimo y use una array de frecuencia freq[] para almacenar el recuento de elementos para los que se establece el bit k-ésimo .
- Para cada elemento de la array, compruebe si el k-ésimo bit de ese elemento está configurado o no . Si se establece el k-ésimo bit , simplemente aumente la frecuencia del k-ésimo bit.
- Recorra la array y para cada elemento arr[i] verifique si el k-ésimo bit de arr[i] está configurado o no.
- Inicialice la suma requerida en 0 para cada índice i .
- Si se establece el k-ésimo bit de arr[i] , significa que también se establecerá el k – ésimo bit de todos los posibles (arr[i] | arr[j]) . Entonces, en este caso, agregue (1 << k) * N a la suma requerida .
- De lo contrario, si el k-ésimo bit de arr[i] no está establecido, significa que el k-ésimo bit de (arr[i] | arr[j]) se establecerá si y solo si el k-ésimo bit de arr[j ] está configurado . Entonces, en este caso, agregue (1 << k) * freq[k] a la suma requerida que se calculó previamente que el k-ésimo bit se establece para el número de elementos de freq[k] .
- Finalmente, imprima el valor de la suma requerida para el índice i .
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 print required sum for
// every valid index i
void printORSumforEachElement(int arr[], int N)
{
// Frequency array to store frequency
// of every k-th bit
int freq[32];
// Initialize frequency array
memset(freq, 0, sizeof freq);
for (int i = 0; i < N; i++) {
for (int k = 0; k < 32; k++) {
// If k-th bit is set, then update
// the frequency of k-th bit
if ((arr[i] & (1 << k)) != 0)
freq[k]++;
}
}
for (int i = 0; i < N; i++) {
// Stores the required sum
// for the current array element
int req_sum = 0;
for (int k = 0; k < 32; k++) {
// If k-th bit is set
if ((arr[i] & (1 << k)) != 0)
req_sum += (1 << k) * N;
// If k-th bit is not set
else
req_sum += (1 << k) * freq[k];
}
// Print the required sum
cout << req_sum << " ";
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 2, 3, 4 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
printORSumforEachElement(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to print required sum for
// every valid index i
static void printORSumforEachElement(int arr[], int N)
{
// Frequency array to store frequency
// of every k-th bit
int []freq = new int[32];
for (int i = 0; i < N; i++)
{
for (int k = 0; k < 32; k++)
{
// If k-th bit is set, then update
// the frequency of k-th bit
if ((arr[i] & (1 << k)) != 0)
freq[k]++;
}
}
for (int i = 0; i < N; i++)
{
// Stores the required sum
// for the current array element
int req_sum = 0;
for (int k = 0; k < 32; k++)
{
// If k-th bit is set
if ((arr[i] & (1 << k)) != 0)
req_sum += (1 << k) * N;
// If k-th bit is not set
else
req_sum += (1 << k) * freq[k];
}
// Print the required sum
System.out.print(req_sum+ " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 1, 2, 3, 4 };
// Size of the array
int N = arr.length;
// Function Call
printORSumforEachElement(arr, N);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to print required sum for # every valid index i def printORSumforEachElement(arr, N): # Frequency array to store frequency # of every k-th bit freq = [0 for i in range(32)] for i in range(N): for k in range(32): # If k-th bit is set, then update # the frequency of k-th bit if ((arr[i] & (1 << k)) != 0): freq[k] += 1 for i in range(N): # Stores the required sum # for the current array element req_sum = 0 for k in range(32): # If k-th bit is set if ((arr[i] & (1 << k)) != 0): req_sum += (1 << k) * N # If k-th bit is not set else: req_sum += (1 << k) * freq[k] # Print the required sum print(req_sum, end = " ") # Driver Code if __name__ == '__main__': # Given array arr = [ 1, 2, 3, 4 ] # Size of the array N = len(arr) # Function Call printORSumforEachElement(arr, N) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG
{
// Function to print required sum for
// every valid index i
static void printORSumforEachElement(int[] arr, int N)
{
// Frequency array to store frequency
// of every k-th bit
int[] freq = new int[32];
for (int i = 0; i < N; i++)
{
for (int k = 0; k < 32; k++)
{
// If k-th bit is set, then update
// the frequency of k-th bit
if ((arr[i] & (1 << k)) != 0)
freq[k]++;
}
}
for (int i = 0; i < N; i++)
{
// Stores the required sum
// for the current array element
int req_sum = 0;
for (int k = 0; k < 32; k++)
{
// If k-th bit is set
if ((arr[i] & (1 << k)) != 0)
req_sum += (1 << k) * N;
// If k-th bit is not set
else
req_sum += (1 << k) * freq[k];
}
// Print the required sum
Console.Write(req_sum + " ");
}
}
// Driver Code
public static void Main()
{
// Given array
int[] arr = { 1, 2, 3, 4 };
// Size of the array
int N = arr.Length;
// Function Call
printORSumforEachElement(arr, N);
}
}
// This code is contributed by chitranayal.
Javascript
<script>
// Javascript program for the above approach
// Function to print required sum for
// every valid index i
function printORSumforEachElement(arr, N)
{
// Frequency array to store frequency
// of every k-th bit
var freq = Array(32).fill(0);
for(var i = 0; i < N; i++)
{
for(var k = 0; k < 32; k++)
{
// If k-th bit is set, then update
// the frequency of k-th bit
if ((arr[i] & (1 << k)) != 0)
freq[k]++;
}
}
for(var i = 0; i < N; i++)
{
// Stores the required sum
// for the current array element
var req_sum = 0;
for(var k = 0; k < 32; k++)
{
// If k-th bit is set
if ((arr[i] & (1 << k)) != 0)
req_sum += (1 << k) * N;
// If k-th bit is not set
else
req_sum += (1 << k) * freq[k];
}
// Print the required sum
document.write(req_sum + " ");
}
}
// Driver Code
// Given array
var arr = [ 1, 2, 3, 4 ];
// Size of the array
var N = arr.length;
// Function Call
printORSumforEachElement(arr, N);
// This code is contributed by rutvik_56
</script>
Producción:
12 14 16 22
Complejidad de Tiempo: O(32 * N)
Espacio Auxiliar: O(m), donde m = 32
Publicación traducida automáticamente
Artículo escrito por kundudinesh007 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA