Dada una array, necesitamos calcular la Suma de bits AND de todos los subconjuntos posibles de la array dada.
Ejemplos:
Input : 1 2 3
Output : 9
For [1, 2, 3], all possible subsets are {1},
{2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
Bitwise AND of these subsets are, 1 + 2 +
3 + 0 + 1 + 2 + 0 = 9.
So, the answer would be 9.
Input : 1 2 3 4
Output : 13
Consulte esta publicación para el enfoque ingenuo de conjunto de bits de conteo , podemos producir todos los subconjuntos usando Power Set y luego calcular Bit-wise Y la suma de todos los subconjuntos. En un mejor enfoque, estamos tratando de calcular qué elemento de la array es responsable de producir la suma en un subconjunto. Comencemos con el bit menos significativo. Para eliminar la contribución de otros bits, calculamos el número Y el bit para todos los números del conjunto. Cualquier subconjunto de esto que contenga un 0 no dará ninguna contribución. Todos los subconjuntos no vacíos que solo constan de 1 darán 1 en contribución. En total habrá 2^n – 1 de tales subconjuntos, cada uno dando 1 en contribución. Lo mismo ocurre con el otro bit. Obtenemos [0, 2, 2], 3 subconjuntos cada uno dando 2. Total 3*1 + 3*2 = 9
Array = {1, 2, 3}
Binary representation
positions 2 1 0
1 0 0 1
2 0 1 0
3 0 1 1
[ 0 2 2 ]
Count set bit for each position
[ 0 3 3 ] subset produced by each
position 2^n -1 i.e. n is total sum
for each position [ 0, 3*2^1, 3*2^0 ]
Now calculate the sum by multiplying
the position value i.e 2^0, 2^1 ... .
0 + 6 + 3 = 9
CPP
// C++ program to calculate sum of Bit-wise
// and sum of all subsets of an array
#include <bits/stdc++.h>
using namespace std;
#define BITS 32
int andSum(int arr[], int n)
{
int ans = 0;
// assuming representation of each element is
// in 32 bit
for (int i = 0; i < BITS; i++) {
int countSetBits = 0;
// iterating array element
for (int j = 0; j < n; j++) {
// Counting the set bit of array in
// ith position
if (arr[j] & (1 << i))
countSetBits++;
}
// counting subset which produce sum when
// particular bit position is set.
int subset = (1 << countSetBits) - 1;
// multiplying every position subset with 2^i
// to count the sum.
subset = (subset * (1 << i));
ans += subset;
}
return ans;
}
// Drivers code
int main()
{
int arr[] = { 1, 2, 3};
int size = sizeof(arr) / sizeof(arr[0]);
cout << andSum(arr, size);
return 0;
}
Java
// Java program to calculate sum of Bit-wise
// and sum of all subsets of an array
class GFG {
static final int BITS = 32;
static int andSum(int arr[], int n)
{
int ans = 0;
// assuming representation of each
// element is in 32 bit
for (int i = 0; i < BITS; i++) {
int countSetBits = 0;
// iterating array element
for (int j = 0; j < n; j++) {
// Counting the set bit of
// array in ith position
if ((arr[j] & (1 << i)) != 0)
countSetBits++;
}
// counting subset which produce
// sum when particular bit
// position is set.
int subset = (1 << countSetBits) - 1;
// multiplying every position
// subset with 2^i to count the
// sum.
subset = (subset * (1 << i));
ans += subset;
}
return ans;
}
// Drivers code
public static void main(String args[])
{
int arr[] = { 1, 2, 3};
int size = 3;
System.out.println (andSum(arr, size));
}
}
// This code is contributed by Arnab Kundu.
Python3
# Python3 program to calculate sum of # Bit-wise and sum of all subsets of # an array BITS = 32; def andSum(arr, n): ans = 0 # assuming representation # of each element is # in 32 bit for i in range(0, BITS): countSetBits = 0 # iterating array element for j in range(0, n) : # Counting the set bit # of array in ith # position if (arr[j] & (1 << i)) : countSetBits = (countSetBits + 1) # counting subset which # produce sum when # particular bit position # is set. subset = ((1 << countSetBits) - 1) # multiplying every position # subset with 2^i to count # the sum. subset = (subset * (1 << i)) ans = ans + subset return ans # Driver code arr = [1, 2, 3] size = len(arr) print (andSum(arr, size)) # This code is contributed by # Manish Shaw (manishshaw1)
C#
// C# program to calculate sum of Bit-wise
// and sum of all subsets of an array
using System;
class GFG {
static int BITS = 32;
static int andSum(int[] arr, int n)
{
int ans = 0;
// assuming representation of each
// element is in 32 bit
for (int i = 0; i < BITS; i++) {
int countSetBits = 0;
// iterating array element
for (int j = 0; j < n; j++) {
// Counting the set bit of
// array in ith position
if ((arr[j] & (1 << i)) != 0)
countSetBits++;
}
// counting subset which produce
// sum when particular bit position
// is set.
int subset = (1 << countSetBits) - 1;
// multiplying every position subset
// with 2^i to count the sum.
subset = (subset * (1 << i));
ans += subset;
}
return ans;
}
// Drivers code
static public void Main()
{
int []arr = { 1, 2, 3};
int size = 3;
Console.WriteLine (andSum(arr, size));
}
}
// This code is contributed by Arnab Kundu.
PHP
<?php
// PHP program to calculate sum of Bit-wise
// and sum of all subsets of an array
$BITS = 32;
function andSum( $arr, $n)
{
global $BITS;
$ans = 0;
// assuming representation
// of each element is
// in 32 bit
for($i = 0; $i < $BITS; $i++)
{
$countSetBits = 0;
// iterating array element
for ( $j = 0; $j < $n; $j++) {
// Counting the set bit
// of array in ith position
if ($arr[$j] & (1 << $i))
$countSetBits++;
}
// counting subset which
// produce sum when
// particular bit position
// is set.
$subset = (1 << $countSetBits) - 1;
// multiplying every position
// subset with 2^i to count
// the sum.
$subset = ($subset * (1 << $i));
$ans += $subset;
}
return $ans;
}
// Driver code
$arr = array(1, 2, 3);
$size = count($arr);
echo andSum($arr, $size);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// javascript program to calculate sum of Bit-wise
// and sum of all subsets of an array
var BITS = 32;
function andSum(arr , n) {
var ans = 0;
// assuming representation of each
// element is in 32 bit
for (i = 0; i < BITS; i++) {
var countSetBits = 0;
// iterating array element
for (j = 0; j < n; j++) {
// Counting the set bit of
// array in ith position
if ((arr[j] & (1 << i)) != 0)
countSetBits++;
}
// counting subset which produce
// sum when particular bit
// position is set.
var subset = (1 << countSetBits) - 1;
// multiplying every position
// subset with 2^i to count the
// sum.
subset = (subset * (1 << i));
ans += subset;
}
return ans;
}
// Drivers code
var arr = [ 1, 2, 3 ];
var size = 3;
document.write(andSum(arr, size));
// This code contributed by gauravrajput1
</script>
Producción:
9
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)