Dada una array de n enteros, encuentre la suma de xor de todos los pares de números en la array.
Ejemplos:
Input : arr[] = {7, 3, 5}
Output : 12
7 ^ 3 = 4
3 ^ 5 = 6
7 ^ 5 = 2
Sum = 4 + 6 + 2
= 12
Input : arr[] = {5, 9, 7, 6}
Output : 47
5 ^ 9 = 12
9 ^ 7 = 14
7 ^ 6 = 1
5 ^ 7 = 2
5 ^ 6 = 3
9 ^ 6 = 15
Sum = 12 + 14 + 1 + 2 + 3 + 15
= 47
Solución ingenua
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 sum of bitwise OR
// of all pairs
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[] = { 5, 9, 7, 6 };
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 sum of bitwise OR
// of all pairs
static int pairORSum(int arr[], int n)
{
// Initialize result
int ans = 0;
// 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[] = { 5, 9, 7, 6 };
int n = arr.length;
System.out.println(pairORSum(arr,
arr.length));
}
}
// This code is contributed by vt_m
Python3
# A Simple Python 3 program to compute # sum of bitwise OR of all pairs # Returns sum of bitwise OR # of all pairs 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 Code arr = [ 5, 9, 7, 6 ] n = len(arr) print(pairORSum(arr, n)) # This code is contributed by Nikita Tiwari.
C#
// A Simple C# program to compute
// sum of bitwise OR of all pairs
using System;
class GFG {
// Returns sum of bitwise OR
// of all pairs
static int pairORSum(int []arr, int n)
{
// Initialize result
int ans = 0;
// 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 = { 5, 9, 7, 6 };
int n = arr.Length;
Console.WriteLine(pairORSum(arr,
arr.Length));
}
}
// This code is contributed by vt_m
PHP
<?php
// A Simple PHP program to compute
// sum of bitwise OR of all pairs
// Returns sum of bitwise OR
// of all pairs
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( 5, 9, 7, 6 );
$n = count($arr);
echo pairORSum($arr, $n) ;
// This code is contributed by anuj_67.
JavaScript
<script>
// A Simple Javascript program to compute
// sum of bitwise OR of all pairs
// Returns sum of bitwise OR
// of all pairs
const pairORSum = (arr, n) => {
let ans = 0; // Initialize result
// Consider all pairs (arr[i], arr[j) such that
// i < j
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
ans += arr[i] ^ arr[j];
return ans;
}
// Driver program to test above function
let arr = [5, 9, 7, 6];
let n = arr.length;
document.write(pairORSum(arr, n));
// This code is contributed by rakeshsahni
</script>
?>
Producción :
47
Solución Eficiente
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 solución optimizada será probar la manipulación de bits . Para implementar la solución, consideramos todos los bits que son 1 y 0 y almacenamos su cuenta en dos variables diferentes. A continuación, multiplique esos recuentos junto con la potencia de 2 elevada a esa posición de bit. Haga esto para todas las posiciones de bits de los números. Su suma sería nuestra respuesta.
¿Cómo funciona esto realmente?
Por ejemplo, mire el bit más a la derecha de todos los números en la array. Suponga que los números a tienen un bit 0 más a la derecha y los números b tienen un bit 1. Luego, de los pares, a*b de ellos tendrán 1 en el bit más a la derecha del XOR. Esto se debe a que hay a*b formas de elegir un número que tenga 0 bits y otro que tenga 1 bit. Por lo tanto, estos bits contribuirán a*b al total de todos los XOR.
En general, al observar el bit n (donde el bit más a la derecha es el 0), cuente cuántos números tienen 0 (llámelo an) y cuántos tienen 1 (llámelo bn). La contribución a la suma final será an*bn*pow(2,n). Debe hacer esto para cada bit y sumar todas estas contribuciones juntas.
Esto se puede hacer en tiempo O(kn), donde k es el número de bits en los valores dados.
Explanation : arr[] = { 7, 3, 5 }
7 = 1 1 1
3 = 0 1 1
5 = 1 0 1
For bit position 0 :
Bits with zero = 0
Bits with one = 3
Answer = 0 * 3 * 2 ^ 0 = 0
Similarly, for bit position 1 :
Bits with zero = 1
Bits with one = 2
Answer = 1 * 2 * 2 ^ 1 = 4
Similarly, for bit position 2 :
Bits with zero = 1
Bits with one = 2
Answer = 1 * 2 * 2 ^ 2 = 8
Final answer = 0 + 4 + 8 = 12
CPP
// An efficient C++ program to compute
// sum of bitwise OR of all pairs
#include <bits/stdc++.h>
using namespace std;
// Returns sum of bitwise OR
// of all pairs
long long int sumXOR(int arr[], int n)
{
long long int sum = 0;
for (int i = 0; i < 32; i++)
{
// Count of zeros and ones
int zc = 0, oc = 0;
// Individual sum at each bit position
long long int idsum = 0;
for (int j = 0; j < n; j++)
{
if (arr[j] % 2 == 0)
zc++;
else
oc++;
arr[j] /= 2;
}
// calculating individual bit sum
idsum = oc * zc * (1 << i);
// final sum
sum += idsum;
}
return sum;
}
int main()
{
long long int sum = 0;
int arr[] = { 5, 9, 7, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
sum = sumXOR(arr, n);
cout << sum;
return 0;
}
Java
// An efficient Java program to compute
// sum of bitwise OR of all pairs
import java.io.*;
class GFG {
// Returns sum of bitwise OR
// of all pairs
static long sumXOR(int arr[], int n)
{
long sum = 0;
for (int i = 0; i < 32; i++)
{
// Count of zeros and ones
int zc = 0, oc = 0;
// Individual sum at each bit position
long idsum = 0;
for (int j = 0; j < n; j++)
{
if (arr[j] % 2 == 0)
zc++;
else
oc++;
arr[j] /= 2;
}
// calculating individual bit sum
idsum = oc * zc * (1 << i);
// final sum
sum += idsum;
}
return sum;
}
// Driver Code
public static void main(String args[])
{
long sum = 0;
int arr[] = { 5, 9, 7, 6 };
int n = arr.length;
sum = sumXOR(arr, n);
System.out.println(sum);
}
}
// This code is contributed by Nikita Tiwari.
Python3
# An efficient Python3 program to compute # sum of bitwise OR of all pair # Returns sum of bitwise OR # of all pairs def sumXOR( arr, n): sum = 0 for i in range(0, 32): # Count of zeros and ones zc = 0 oc = 0 # Individual sum at each bit position idsum = 0 for j in range(0, n): if (arr[j] % 2 == 0): zc = zc + 1 else: oc = oc + 1 arr[j] = int(arr[j] / 2) # calculating individual bit sum idsum = oc * zc * (1 << i) # final sum sum = sum + idsum; return sum # driver function sum = 0 arr = [ 5, 9, 7, 6 ] n = len(arr) sum = sumXOR(arr, n); print (sum) # This code is contributed by saloni1297
C#
// An efficient C# program to compute
// sum of bitwise OR of all pairs
using System;
class GFG {
// Returns sum of bitwise OR
// of all pairs
static long sumXOR(int []arr, int n)
{
long sum = 0;
for (int i = 0; i < 32; i++)
{
// Count of zeros and ones
int zc = 0, oc = 0;
// Individual sum at each bit position
long idsum = 0;
for (int j = 0; j < n; j++)
{
if (arr[j] % 2 == 0)
zc++;
else
oc++;
arr[j] /= 2;
}
// calculating individual bit sum
idsum = oc * zc * (1 << i);
// final sum
sum += idsum;
}
return sum;
}
// Driver Code
public static void Main()
{
long sum = 0;
int []arr = { 5, 9, 7, 6 };
int n = arr.Length;
sum = sumXOR(arr, n);
Console.WriteLine(sum);
}
}
// This code is contributed by vt_m.
PHP
<?php
// An efficient PHP program to compute
// sum of bitwise OR of all pairs
// Returns sum of bitwise OR
// of all pairs
function sumXOR($arr, $n)
{
$sum = 0;
for ($i = 0; $i < 32; $i++)
{
// Count of zeros and ones
$zc = 0; $oc = 0;
// Individual sum at each
// bit position
$idsum = 0;
for ($j = 0; $j < $n; $j++)
{
if ($arr[$j] % 2 == 0)
$zc++;
else
$oc++;
$arr[$j] /= 2;
}
// calculating individual bit sum
$idsum = $oc * $zc * (1 << $i);
// final sum
$sum += $idsum;
}
return $sum;
}
// Driver code
$sum = 0;
$arr = array( 5, 9, 7, 6 );
$n = count($arr);
$sum = sumXOR($arr, $n);
echo $sum;
// This code is contributed by anuj_67
JavaScript
<script>
// An efficient JavaScript program to compute
// sum of bitwise OR of all pairs
// Returns sum of bitwise OR
// of all pairs
const sumXOR = (arr, n) => {
let sum = 0;
for (let i = 0; i < 32; i++) {
// Count of zeros and ones
let zc = 0, oc = 0;
// Individual sum at each bit position
let idsum = 0;
for (let j = 0; j < n; j++) {
if (arr[j] % 2 == 0)
zc++;
else
oc++;
arr[j] = parseInt(arr[j] / 2);
}
// calculating individual bit sum
idsum = oc * zc * (1 << i);
// final sum
sum += idsum;
}
return sum;
}
let sum = 0;
let arr = [5, 9, 7, 6];
let n = arr.length;
sum = sumXOR(arr, n);
document.write(sum);
// This code is contributed by rakeshsahni
</script>
?>
Producción:
47
Publicación traducida automáticamente
Artículo escrito por premkagrani y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA