Dada una array arr[] de tamaño n, necesitamos encontrar la suma de todos los valores que provienen de la operación OR de todos los elementos de los subconjuntos.
Prerrequisitos: Subconjunto Suma del conjunto dado
Ejemplos:
Input : arr[] = {1, 2, 3}
Output : 18
Total Subsets = 23 -1= 7
1 = 1
2 = 2
3 = 3
1 | 2 = 3
1 | 3 = 3
2 | 3 = 3
1 | 2 | 3 = 3
0(empty subset)
Now SUM of all these ORs = 1 + 2 + 3 + 3 +
3 + 3 + 3
= 18
Input : arr[] = {1, 2, 3}
Output : 18
Un enfoque ingenuo es tomar el OR de todas las combinaciones posibles de elementos array[] y luego realizar la suma de todos los valores. La complejidad temporal de este enfoque crece exponencialmente, por lo que no sería mejor para un valor grande de n.
Un enfoque eficiente es encontrar el patrón con respecto a la propiedad de OR. Ahora nuevamente considere el subconjunto en forma binaria como:
1 = 001
2 = 010
3 = 011
1 | 2 = 011
1 | 3 = 011
2 | 3 = 011
1|2|3 = 011
En lugar de tomar el OR de todos los elementos posibles de la array, aquí consideraremos todos los subconjuntos posibles con el i-ésimo bit 1.
Ahora, considere el i-ésimo bit en todos los OR resultantes, es cero solo si todos los i-ésimo bits de elementos en el subconjunto es 0.
Número de subconjuntos con i-ésimo bit 1 = total de subconjuntos posibles – subconjuntos con todos los i-ésimos bits 0. Aquí, subconjuntos totales = 2^n – 1 y subconjuntos con todos los i-ésimos bits 0 = 2^( recuento de ceros en el i-ésimo bit de todos los elementos de la array) – 1. Ahora, subconjunto total O con i-ésimo bit 1 = (2^n-1)-(2^(recuento de ceros en i-ésimo bit)-1). Valor total aportado por esos bits con valor 1 = subconjunto total O con i-ésimo bit 1 *(2^i).
Ahora, suma total = (subconjunto total con i-ésimo bit 1) * 2^i + (subconjunto total con i+1º bit 1) * 2^(i+1) + ……… + (subconjunto total con 32 bit 1) * 2^32.
C++
// CPP code to find the OR_SUM
#include <bits/stdc++.h>
using namespace std;
#define INT_SIZE 32
// function to find the OR_SUM
int ORsum(int arr[], int n)
{
// create an array of size 32
// and store the sum of bits
// with value 0 at every index.
int zerocnt[INT_SIZE] = { 0 };
for (int i = 0; i < INT_SIZE; i++)
for (int j = 0; j < n; j++)
if (!(arr[j] & 1 << i))
zerocnt[i] += 1;
// for each index the OR sum contributed
// by that bit of subset will be 2^(bit index)
// now the OR of the bits is 0 only if
// all the ith bit of the elements in subset
// is 0.
int ans = 0;
for (int i = 0; i < INT_SIZE; i++)
{
ans += ((pow(2, n) - 1) -
(pow(2, zerocnt[i]) - 1)) *
pow(2, i);
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << ORsum(arr, size);
return 0;
}
Java
// Java code to find
// the OR_SUM
import java.io.*;
class GFG {
static int INT_SIZE = 32;
// function to find
// the OR_SUM
static int ORsum(int []arr, int n)
{
// create an array of size 32
// and store the sum of bits
// with value 0 at every index.
int zerocnt[] = new int[INT_SIZE] ;
for (int i = 0; i < INT_SIZE; i++)
for (int j = 0; j < n; j++)
if ((arr[j] & 1 << i) == 0)
zerocnt[i] += 1;
// for each index the OR
// sum contributed by that
// bit of subset will be
// 2^(bit index) now the OR
// of the bits is 0 only if
// all the ith bit of the
// elements in subset is 0.
int ans = 0;
for (int i = 0; i < INT_SIZE; i++)
{
ans += ((Math.pow(2, n) - 1) -
(Math.pow(2, zerocnt[i]) - 1)) *
Math.pow(2, i);
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3 };
int size = arr.length;
System.out.println(ORsum(arr, size));
}
}
// This code is contributed by Sam007
Python3
INT_SIZE = 32 # function to find the OR_SUM def ORsum(arr, n): # create an array of size 32 # and store the sum of bits # with value 0 at every index. zerocnt = [0 for i in range(INT_SIZE)] for i in range(INT_SIZE): for j in range(n): if not (arr[j] & (1 << i)): zerocnt[i] += 1 # for each index the OR sum contributed # by that bit of subset will be 2^(bit index) # now the OR of the bits is 0 only if # all the ith bit of the elements in subset # is 0. ans = 0 for i in range(INT_SIZE): ans += ((2 ** n - 1) - (2 ** zerocnt[i] - 1)) * 2 ** i return ans # Driver code if __name__ == "__main__": arr= [1, 2, 3] size = len(arr) print(ORsum(arr, size)) # This code is contributed by vaibhav29498
C#
// C# code to find
// the OR_SUM
using System;
class GFG {
static int INT_SIZE = 32;
// function to find
// the OR_SUM
static int ORsum(int []arr, int n)
{
// create an array of size 32
// and store the sum of bits
// with value 0 at every index.
int []zerocnt = new int[INT_SIZE] ;
for (int i = 0; i < INT_SIZE; i++)
for (int j = 0; j < n; j++)
if ((arr[j] & 1 << i) == 0)
zerocnt[i] += 1;
// for each index the OR
// sum contributed by that
// bit of subset will be
// 2^(bit index) now the OR
// of the bits is 0 only if
// all the ith bit of the
// elements in subset is 0.
int ans = 0;
for (int i = 0; i < INT_SIZE; i++)
{
ans += (int)(((Math.Pow(2, n) - 1) -
(Math.Pow(2, zerocnt[i]) - 1)) *
Math.Pow(2, i));
}
return ans;
}
// Driver Code
public static void Main()
{
int []arr = {1, 2, 3};
int size = arr.Length;
Console.Write(ORsum(arr, size));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP code to find the OR_SUM
$INT_SIZE = 32;
// function to find the OR_SUM
function ORsum(&$arr, $n)
{
global $INT_SIZE;
// create an array of size 32
// and store the sum of bits
// with value 0 at every index.
$zerocnt = array_fill(0, $INT_SIZE, NULL);
for ($i = 0; $i < $INT_SIZE; $i++)
for ($j = 0; $j < $n; $j++)
if (!($arr[$j] & 1 << $i))
$zerocnt[$i] += 1;
// for each index the OR sum contributed
// by that bit of subset will be 2^(bit index)
// now the OR of the bits is 0 only if
// all the ith bit of the elements in
// subset is 0.
$ans = 0;
for ($i = 0; $i < $INT_SIZE; $i++)
{
$ans += ((pow(2, $n) - 1) -
(pow(2, $zerocnt[$i]) - 1)) *
pow(2, $i);
}
return $ans;
}
// Driver code
$arr = array(1, 2, 3);
$size = sizeof($arr);
echo ORsum($arr, $size);
// This code is contributed by ita_c
?>
Javascript
<script>
// JavaScript code to find the OR_SUM
let INT_SIZE = 32;
// function to find the OR_SUM
function ORsum(arr, n)
{
// create an array of size 32
// and store the sum of bits
// with value 0 at every index.
let zerocnt = new Uint8Array(INT_SIZE);
for (let i = 0; i < INT_SIZE; i++)
for (let j = 0; j < n; j++)
if (!(arr[j] & 1 << i))
zerocnt[i] += 1;
// for each index the OR sum contributed
// by that bit of subset will be 2^(bit index)
// now the OR of the bits is 0 only if
// all the ith bit of the elements in subset
// is 0.
let ans = 0;
for (let i = 0; i < INT_SIZE; i++)
{
ans += ((Math.pow(2, n) - 1) -
(Math.pow(2, zerocnt[i]) - 1)) *
Math.pow(2, i);
}
return ans;
}
// Driver code
let arr = [ 1, 2, 3 ];
let size = arr.length;
document.write(ORsum(arr, size));
// This code is contributed by Surbhi Tyagi.
</script>
18
Complejidad temporal: O(n)
Espacio auxiliar: O(n)