Dado un arreglo “arr[0..n-1]” de enteros. La tarea es calcular la suma de Bitwise OR de todos los pares, es decir, calcular la suma de “ arr[i] | arr[j] ” para todos los pares en la array dada donde i < j. Aquí ‘|’ es un operador OR bit a bit. La complejidad de tiempo esperada es O(n).
Ejemplos:
Input: arr[] = {5, 10, 15}
Output: 15
Required Value = (5 | 10) + (5 | 15) + (10 | 15)
= 15 + 15 + 15
= 45
Input: arr[] = {1, 2, 3, 4}
Output: 3
Required Value = (1 | 2) + (1 | 3) + (1 | 4) +
(2 | 3) + (2 | 4) + (3 | 4)
= 3 + 3 + 5 + 3 + 6 + 7
= 27
Un enfoque de fuerza bruta consiste en ejecutar dos bucles y la complejidad del tiempo es O(n 2 ).
C++
// A Simple C++ program to compute sum of bitwise OR
// of all pairs
#include <bits/stdc++.h>
using namespace std;
// Returns value of "arr[0] | arr[1] + arr[0] | arr[2] +
// ... arr[i] | arr[j] + ..... arr[n-2] | arr[n-1]"
int pairORSum(int arr[], int n)
{
int ans = 0; // Initialize result
// Consider all pairs (arr[i], arr[j) such that
// i < j
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
ans += arr[i] | arr[j];
return ans;
}
// Driver program to test above function
int main()
{
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << pairORSum(arr, n) << endl;
return 0;
}
Java
// A Simple Java program to compute
// sum of bitwise OR of all pairs
import java.io.*;
class GFG {
// Returns value of "arr[0] | arr[1] +
// arr[0] | arr[2] + ... arr[i] | arr[j] +
// ..... arr[n-2] | arr[n-1]"
static int pairORSum(int arr[], int n)
{
int ans = 0; // Initialize result
// Consider all pairs (arr[i], arr[j)
// such that i < j
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
ans += arr[i] | arr[j];
return ans;
}
// Driver program to test above function
public static void main(String args[])
{
int arr[] = { 1, 2, 3, 4 };
int n = arr.length;
System.out.println(pairORSum(arr, n));
}
}
Python3
# A Simple Python 3 program to compute # sum of bitwise OR of all pairs # Returns value of "arr[0] | arr[1] + # arr[0] | arr[2] + ... arr[i] | arr[j] + # ..... arr[n-2] | arr[n-1]" def pairORSum(arr, n) : ans = 0 # Initialize result # Consider all pairs (arr[i], arr[j) # such that i < j for i in range(0, n) : for j in range((i + 1), n) : ans = ans + arr[i] | arr[j] return ans # Driver program to test above function arr = [1, 2, 3, 4] n = len(arr) print(pairORSum(arr, n))
C#
// A Simple C# program to compute
// sum of bitwise OR of all pairs
using System;
class GFG {
// Returns value of "arr[0] | arr[1] +
// arr[0] | arr[2] + ... arr[i] | arr[j] +
// ..... arr[n-2] | arr[n-1]"
static int pairORSum(int[] arr, int n)
{
int ans = 0; // Initialize result
// Consider all pairs (arr[i], arr[j)
// such that i < j
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
ans += arr[i] | arr[j];
return ans;
}
// Driver program to test above function
public static void Main()
{
int[] arr = { 1, 2, 3, 4 };
int n = arr.Length;
Console.Write(pairORSum(arr, n));
}
}
PHP
<?php
// A Simple PHP program to
// compute sum of bitwise
// OR of all pairs
// Returns value of "arr[0] |
// arr[1] + arr[0] | arr[2] +
// ... arr[i] | arr[j] + .....
// arr[n-2] | arr[n-1]"
function pairORSum($arr, $n)
{
// Initialize result
$ans = 0;
// Consider all pairs (arr[i],
// arr[j) such that i < j
for ($i = 0; $i < $n; $i++)
for ( $j = $i + 1; $j < $n; $j++)
$ans += $arr[$i] | $arr[$j];
return $ans;
}
// Driver Code
$arr = array(1, 2, 3, 4);
$n = sizeof($arr) ;
echo pairORSum($arr, $n), "\n";
?>
Javascript
<script>
// A Simple Javascript program to compute sum of bitwise OR
// of all pairs
// Returns value of "arr[0] | arr[1] + arr[0] | arr[2] +
// ... arr[i] | arr[j] + ..... arr[n-2] | arr[n-1]"
function pairORSum(arr, n)
{
var ans = 0; // Initialize result
// Consider all pairs (arr[i], arr[j) such that
// i < j
for (var i = 0; i < n; i++)
for (var j = i + 1; j < n; j++)
ans += arr[i] | arr[j];
return ans;
}
// Driver program to test above function
var arr = [1, 2, 3, 4];
var n = arr.length;
document.write( pairORSum(arr, n));
</script>
Producción:
27
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(1)
Una Solución Eficiente puede resolver este problema en tiempo O(n). La suposición aquí es que los números enteros se representan usando 32 bits.
La idea es contar el número de bits establecidos en cada i-ésima posición (i>=0 && i<=31). Cualquier i-ésimo bit del AND de dos números es 1 si y sólo si el bit correspondiente en ambos números es igual a 1.
Sea k1 el recuento de bits establecidos en la i-ésima posición. El número total de pares con i-ésimo bit establecido sería k1 C 2 = k1*(k1-1)/2 (Cuenta k1 significa que hay k1 números que tienen i-ésimo bit establecido). Cada uno de estos pares suma 2 ia la suma total. De manera similar, hay valores k0 totales que no tienen bits establecidos en la i-ésima posición. Ahora cada elemento (que no ha establecido el bit en la i-ésima posición puede formar pares con k1 elementos (es decir, aquellos elementos que han establecido bits en la i-ésima posición), por lo que hay un total de k1 * k0 pares y cada dicho par también suma 2 i a la suma total
sum = sum + (1<<i) * (k1*(k1-1)/2) + (1<<i) * (k1*k0)
Esta idea es similar a encontrar la suma de las diferencias de bits entre todos los pares A
continuación se muestra la implementación del enfoque anterior:
C++
// An efficient C++ program to compute sum of bitwise OR
// of all pairs
#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
// Returns value of "arr[0] | arr[1] + arr[0] | arr[2] +
// ... arr[i] | arr[j] + ..... arr[n-2] | arr[n-1]"
LLI pairORSum(LLI arr[], LLI n)
{
LLI ans = 0; // Initialize result
// Traverse over all bits
for (LLI i = 0; i < 32; i++) {
// Count number of elements with the i'th bit set(ie., 1)
LLI k1 = 0; // Initialize the count
// Count number of elements with i’th bit not-set(ie., 0) `
LLI k0 = 0; // Initialize the count
for (LLI j = 0; j < n; j++) {
if ((arr[j] & (1 << i))) // if i'th bit is set
k1++;
else
k0++;
}
// There are k1 set bits, means k1(k1-1)/2 pairs. k1C2
// There are k0 not-set bits and k1 set bits so total pairs will be k1*k0.
// Every pair adds 2^i to the answer. Therefore,
ans = ans + (1 << i) * (k1 * (k1 - 1) / 2) + (1 << i) * (k1 * k0);
}
return ans;
}
// Driver program to test the above function
int main()
{
LLI arr[] = { 1, 2, 3, 4 };
LLI n = sizeof(arr) / sizeof(arr[0]);
cout << pairORSum(arr, n) << endl;
return 0;
}
Java
// An efficient Java program to compute
// sum of bitwise OR of all pairs
import java.io.*;
class GFG {
// Returns value of "arr[0] | arr[1] + arr[0] | arr[2] +
// ... arr[i] | arr[j] + ..... arr[n-2] | arr[n-1]"
static int pairORSum(int arr[], int n)
{
int ans = 0; // Initialize result
// Traverse over all bits
for (int i = 0; i < 32; i++) {
// Count number of elements with the ith bit set(ie., 1)
int k1 = 0; // Initialize the count
// Count number of elements with ith bit not-set(ie., 0) `
int k0 = 0; // Initialize the count
for (int j = 0; j < n; j++) {
if ((arr[j] & (1 << i)) != 0) // if i'th bit is set
k1++;
else
k0++;
}
// There are k1 set bits, means k1(k1-1)/2 pairs. k1C2
// There are k0 not-set bits and k1 set bits so total pairs will be k1*k0.
// Every pair adds 2^i to the answer. Therefore,
ans = ans + (1 << i) * (k1 * (k1 - 1) / 2) + (1 << i) * (k1 * k0);
}
return ans;
}
// Driver program to test above function
public static void main(String args[])
{
int arr[] = { 1, 2, 3, 4 };
int n = arr.length;
System.out.println(pairORSum(arr, n));
}
}
Python3
# An efficient Python 3 program to # compute the sum of bitwise OR of all pairs # Returns value of "arr[0] | arr[1] + arr[0] | arr[2] + # ... arr[i] | arr[j] + ..... arr[n-2] | arr[n-1]" def pairORSum(arr, n) : # Initialize result ans = 0 # Traverse over all bits for i in range(0, 32) : # Count number of elements with the i'th bit set(ie., 1) k1 = 0 # Count number of elements with i’th bit not-set(ie., 0) ` k0 = 0 for j in range(0, n) : if( (arr[j] & (1<<i)) ): # if i'th bit is set k1 = k1 + 1 else : k0 = k0 + 1 # There are k1 set bits, means k1(k1-1)/2 pairs. k1C2 # There are k0 not-set bits and k1 set bits so total pairs will be k1 * k0. # Every pair adds 2 ^ i to the answer. Therefore, ans = ans + (1<<i) * (k1*(k1-1)//2) + (1<<i) * (k1 * k0) return ans # Driver program to test above function arr = [1, 2, 3, 4] n = len(arr) print(pairORSum(arr, n))
C#
// An efficient C# program to compute
// sum of bitwise OR of all pairs
using System;
class GFG {
// Returns value of "arr[0] | arr[1] + arr[0] | arr[2] +
// ... arr[i] | arr[j] + ..... arr[n-2] | arr[n-1]"
static int pairORSum(int[] arr, int n)
{
int ans = 0; // Initialize result
// Traverse over all bits
for (int i = 0; i < 32; i++) {
// Count number of elements with the ith bit set(ie., 1)
int k1 = 0; // Initialize the count
// Count number of elements with ith bit not-set(ie., 0) `
int k0 = 0; // Initialize the count
for (int j = 0; j < n; j++) {
// if i'th bit is set
if ((arr[j] & (1 << i)) != 0)
k1++;
else
k0++;
}
// There are k1 set bits, means k1(k1-1)/2 pairs. k1C2
// There are k0 not-set bits and k1 set bits so total pairs will be k1*k0.
// Every pair adds 2^i to the answer. Therefore,
ans = ans + (1 << i) * (k1 * (k1 - 1) / 2) + (1 << i) * (k1 * k0);
}
return ans;
}
// Driver program to test above function
public static void Main()
{
int[] arr = new int[] { 1, 2, 3, 4 };
int n = arr.Length;
Console.Write(pairORSum(arr, n));
}
}
PHP
<?php
// An efficient PHP program to compute
// sum of bitwise OR of all pairs
// Returns value of "arr[0] | arr[1] + arr[0] | arr[2] +
// ... arr[i] | arr[j] + ..... arr[n-2] | arr[n-1]"
function pairORSum($arr, $n)
{
$ans = 0; // Initialize result
// Traverse over all bits
for ( $i = 0; $i < 32; $i++){
// Count number of elements with the ith bit set(ie., 1)
$k1 = 0; // Initialize the count
// Count number of elements with ith bit not-set(ie., 0) `
$k0 = 0; // Initialize the count
for ( $j = 0; $j < $n; $j++){
if ( ($arr[$j] & (1 << $i))) // if i'th bit is set
$k1++;
else
$k0++;
}
// There are k1 set bits, means k1(k1-1)/2 pairs. k1C2
// There are k0 not-set bits and k1 set bits so total pairs will be k1*k0.
// Every pair adds 2^i to the answer. Therefore,
$ans = $ans + (1<<$i) * ($k1*($k1-1)/2) + (1<<$i) * ($k1*$k0) ;
}
return $ans;
}
// Driver Code
$arr = array(1, 2, 3, 4);
$n = sizeof($arr);
echo pairORSum($arr, $n) ;
?>
Javascript
<script>
// An efficient Javascript program
// to compute sum of bitwise OR
// of all pairs
// Returns value of "arr[0] | arr[1] + arr[0] | arr[2] +
// ... arr[i] | arr[j] + ..... arr[n-2] | arr[n-1]"
function pairORSum( arr, n)
{
var ans = 0; // Initialize result
// Traverse over all bits
for (var i = 0; i < 32; i++) {
// Count number of elements
// with the i'th bit set(ie., 1)
var k1 = 0; // Initialize the count
// Count number of elements with
// i’th bit not-set(ie., 0) `
var k0 = 0; // Initialize the count
for (var j = 0; j < n; j++) {
if ((arr[j] & (1 << i))) // if i'th bit is set
k1++;
else
k0++;
}
// There are k1 set bits,
// means k1(k1-1)/2 pairs. k1C2
// There are k0 not-set bits and
// k1 set bits so total pairs will be k1*k0.
// Every pair adds 2^i to the answer. Therefore,
ans = ans + (1 << i) * (k1 * (k1 - 1) / 2) +
(1 << i) * (k1 * k0);
}
return ans;
}
// Driver program to test the above function
var arr = [1, 2, 3, 4];
var n = arr.length;
document.write( pairORSum(arr, n));
</script>
Salida :
27
Complejidad de Tiempo: O(n * 32)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Chandan_Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA