给定一个整数数组“arr[0..n-1]”，计算给定数组中所有对的“arr[i]&arr[j]”之和，其中i
null
Input: arr[] = {5, 10, 15}Output: 15Required Value = (5 & 10) + (5 & 15) + (10 & 15) = 0 + 5 + 10 = 15Input: arr[] = {1, 2, 3, 4}Output: 3Required Value = (1 & 2) + (1 & 3) + (1 & 4) + (2 & 3) + (2 & 4) + (3 & 4) = 0 + 1 + 0 + 2 + 0 + 0 = 3
A. 蛮力 方法是运行两个循环，时间复杂度为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; } |
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 Nikita Tiwari.*/ |
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 ), "" ; // 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> |
输出：
15
时间复杂性： O（n） 2. )
辅助空间： O（1）
一 有效解决方案 可以在O（n）时间内解决这个问题。这里的假设是整数用32位表示。 其思想是计算每个i位置（i>=0&&i<=31）的设置位数。当两个数字中的相应位都等于1时，两个数字的AND的任何第i位都是1。 设k为第i位的设定位计数。第i个设置位的总对数为 K C 2. =k*（k-1）/2（计数k表示有k个数有第i个设定位）。每一对加2 我 总而言之。同样，我们为所有其他地方工作，并将总和加到最终答案中。 这个想法类似于 这 .以下是实施情况。
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; } |
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)); } } /*This code is contributed by Nikita Tiwari.*/ |
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> |
输出：
15
时间复杂性： O（n）
辅助空间： O（1）
本文由 埃克塔·戈尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
