Dada una array “arr[0..n-1]” de enteros, calcule la suma de “arr[i] & arr[j]” para todos los pares dados donde i < j. Aquí & es un operador AND 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)
= 0 + 5 + 10
= 15
Input: arr[] = {1, 2, 3, 4}
Output: 3
Required Value = (1 & 2) + (1 & 3) + (1 & 4) +
(2 & 3) + (2 & 4) + (3 & 4)
= 0 + 1 + 0 + 2 + 0 + 0
= 3
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 AND
// 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 pairAndSum(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, 10, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << pairAndSum(arr, n) << endl;
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// A Simple C++ program to compute sum of bitwise AND
// of all pairs
#include <stdio.h>
// Returns value of "arr[0] & arr[1] + arr[0] & arr[2] +
// ... arr[i] & arr[j] + ..... arr[n-2] & arr[n-1]"
int pairAndSum(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, 10, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d\n",pairAndSum(arr, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// A Simple Java program to compute
// sum of bitwise AND 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 pairAndSum(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[] = { 5, 10, 15 };
int n = arr.length;
System.out.println(pairAndSum(arr, n));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# A Simple Python 3 program to compute # sum of bitwise AND 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 pairAndSum(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 = [5, 10, 15] n = len(arr) print(pairAndSum(arr, n)) # This code is contributed by Nikita Tiwari.
C#
// A Simple C# program to compute
// sum of bitwise AND 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 pairAndSum(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 = {5, 10, 15};
int n = arr.Length;
Console.Write(pairAndSum(arr, n) );
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A Simple PHP program to
// compute sum of bitwise
// AND 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 pairAndSum($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, 10, 15);
$n = sizeof($arr) ;
echo pairAndSum($arr, $n), "\n";
// This code is contributed by m_kit
?>
Javascript
<script>
// A Simple Javascript program to compute
// sum of bitwise AND 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 pairAndSum(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;
}
let arr = [5, 10, 15];
let n = arr.length;
document.write(pairAndSum(arr, n));
</script>
Producción :
15
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 k el recuento de bits establecidos en la i-ésima posición. El número total de pares con i-ésimo bit establecido sería k C 2 = k*(k-1)/2 (Cuenta k significa que hay k números que tienen i-ésimo bit establecido). Cada uno de estos pares suma 2 i a la suma total. De manera similar, trabajamos para todos los demás lugares y agregamos la suma a nuestra respuesta final.
Esta idea es similar a esta . A continuación se muestra la implementación.
C++
// An efficient C++ program to compute sum of bitwise AND
// 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 pairAndSum(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 i'th bit set
int k = 0; // Initialize the count
for (int j = 0; j < n; j++)
if ((arr[j] & (1 << i)))
k++;
// There are k set bits, means k(k-1)/2 pairs.
// Every pair adds 2^i to the answer. Therefore,
// we add "2^i * [k*(k-1)/2]" to the answer.
ans += (1 << i) * (k * (k - 1) / 2);
}
return ans;
}
// Driver program to test above function
int main()
{
int arr[] = { 5, 10, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << pairAndSum(arr, n) << endl;
return 0;
}
C
// An efficient C++ program to compute sum of bitwise AND
// of all pairs
#include <stdio.h>
// Returns value of "arr[0] & arr[1] + arr[0] & arr[2] +
// ... arr[i] & arr[j] + ..... arr[n-2] & arr[n-1]"
int pairAndSum(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 i'th bit set
int k = 0; // Initialize the count
for (int j = 0; j < n; j++)
if ((arr[j] & (1 << i)))
k++;
// There are k set bits, means k(k-1)/2 pairs.
// Every pair adds 2^i to the answer. Therefore,
// we add "2^i * [k*(k-1)/2]" to the answer.
ans += (1 << i) * (k * (k - 1) / 2);
}
return ans;
}
// Driver program to test above function
int main()
{
int arr[] = { 5, 10, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d\n",pairAndSum(arr, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// An efficient Java program to compute
// sum of bitwise AND 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 pairAndSum(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 i'th bit set
// Initialize the count
int k = 0;
for (int j = 0; j < n; j++) {
if ((arr[j] & (1 << i)) != 0)
k++;
}
// There are k set bits, means k(k-1)/2 pairs.
// Every pair adds 2^i to the answer. Therefore,
// we add "2^i * [k*(k-1)/2]" to the answer.
ans += (1 << i) * (k * (k - 1) / 2);
}
return ans;
}
// Driver program to test above function
public static void main(String args[])
{
int arr[] = { 5, 10, 15 };
int n = arr.length;
System.out.println(pairAndSum(arr, n));
}
}
// An efficient C++ program to compute sum of bitwise AND
// of all pairs
#include <stdio.h>
// Returns value of "arr[0] & arr[1] + arr[0] & arr[2] +
// ... arr[i] & arr[j] + ..... arr[n-2] & arr[n-1]"
int pairAndSum(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 i'th bit set
int k = 0; // Initialize the count
for (int j = 0; j < n; j++)
if ((arr[j] & (1 << i)))
k++;
// There are k set bits, means k(k-1)/2 pairs.
// Every pair adds 2^i to the answer. Therefore,
// we add "2^i * [k*(k-1)/2]" to the answer.
ans += (1 << i) * (k * (k - 1) / 2);
}
return ans;
}
// Driver program to test above function
int main()
{
int arr[] = { 5, 10, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d\n",pairAndSum(arr, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# An efficient Python 3 program to # compute sum of bitwise AND 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 pairAndSum(arr, n) : ans = 0 # Initialize result # Traverse over all bits for i in range(0,32) : # Count number of elements with i'th bit set # Initialize the count k = 0 for j in range(0,n) : if ( (arr[j] & (1 << i)) ) : k = k + 1 # There are k set bits, means k(k-1)/2 pairs. # Every pair adds 2^i to the answer. Therefore, # we add "2^i * [k*(k-1)/2]" to the answer. ans = ans + (1 << i) * (k * (k - 1) // 2) return ans # Driver program to test above function arr = [5, 10, 15] n = len(arr) print(pairAndSum(arr, n)) # This code is contributed by Nikita Tiwari.
C#
// An efficient C# program to compute
// sum of bitwise AND 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 pairAndSum(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
// i'th bit set Initialize the count
int k = 0;
for (int j = 0; j < n; j++)
{
if ((arr[j] & (1 << i))!=0)
k++;
}
// There are k set bits, means
// k(k-1)/2 pairs. Every pair
// adds 2^i to the answer.
// Therefore, we add "2^i *
// [k*(k-1)/2]" to the answer.
ans += (1 << i) * (k * (k - 1)/2);
}
return ans;
}
// Driver program to test above function
public static void Main()
{
int []arr = new int[]{5, 10, 15};
int n = arr.Length;
Console.Write(pairAndSum(arr, n));
}
}
/* This code is contributed by smitha*/
PHP
<?php
// An efficient PHP program to
// compute sum of bitwise AND
// 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 pairAndSum($arr, $n)
{
// Initialize result
$ans = 0;
// Traverse over all bits
for ($i = 0; $i < 32; $i++)
{
// Count number of elements
// with i'th bit set
// Initialize the count
$k = 0;
for ($j = 0; $j < $n; $j++)
if (($arr[$j] & (1 << $i)) )
$k++;
// There are k set bits,
// means k(k-1)/2 pairs.
// Every pair adds 2^i to
// the answer. Therefore,
// we add "2^i * [k*(k-1)/2]"
// to the answer.
$ans += (1 << $i) * ($k * ($k - 1) / 2);
}
return $ans;
}
// Driver Code
$arr = array(5, 10, 15);
$n = sizeof($arr);
echo pairAndSum($arr, $n) ;
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// An efficient Javascript program to compute
// sum of bitwise AND 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 pairAndSum(arr, n)
{
let ans = 0; // Initialize result
// Traverse over all bits
for (let i = 0; i < 32; i++)
{
// Count number of elements with
// i'th bit set Initialize the count
let k = 0;
for (let j = 0; j < n; j++)
{
if ((arr[j] & (1 << i))!=0)
k++;
}
// There are k set bits, means
// k(k-1)/2 pairs. Every pair
// adds 2^i to the answer.
// Therefore, we add "2^i *
// [k*(k-1)/2]" to the answer.
ans += (1 << i) * (k * (k - 1)/2);
}
return ans;
}
let arr = [5, 10, 15];
let n = arr.length;
document.write(pairAndSum(arr, n));
// This code is contributed by rameshtravel07.
</script>
Producción:
15
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Ekta Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA