给定一个大小为n和整数k的数组，对数组中两个数的二进制表示形式中正好有k位不同的所有对进行计数。 输入数组的元素值很小，可能重复很多次。 例如：
null
Input: arr[] = {2, 4, 1, 3, 1} k = 2 Output: 5Explanation:There are only 4 pairs which differs in exactly 2 bits of binary representation:(2, 4), (1, 2) [Two times] and (4, 1)[Two times]Input : arr[] = {2, 1, 2, 1} k = 2Output : 4
我们强烈建议您在继续解决方案之前单击此处并进行练习。
天真的方法
蛮力是在另一个循环中运行两个循环，逐个选择对，并对两个元素进行异或运算。XORed值的结果包含两个元素中不同的一组位。现在我们只需要计算总的设置位，这样我们就可以将其与值K进行比较。 以下是上述方法的实施情况：
C++
// C++ program to count all pairs with bit difference // as k #include<bits/stdc++.h> using namespace std; // Utility function to count total ones in a number int bitCount( int n) { int count = 0; while (n) { if (n & 1) ++count; n >>= 1; } return count; } // Function to count pairs of K different bits long long countPairsWithKDiff( int arr[], int n, int k) { long long ans = 0; // initialize final answer for ( int i = 0; i < n-1; ++i) { for ( int j = i + 1; j < n; ++j) { int xoredNum = arr[i] ^ arr[j]; // Check for K differ bit if (k == bitCount(xoredNum)) ++ans; } } return ans; } // Driver code int main() { int k = 2; int arr[] = {2, 4, 1, 3, 1}; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Total pairs for k = " << k << " are " << countPairsWithKDiff(arr, n, k) << "" ; return 0; } |
JAVA
// Java program to count all pairs with bit difference // as k import java.io.*; class GFG { // Utility function to count total ones in a number static int bitCount( int n) { int count = 0 ; while (n> 0 ) { if ((n & 1 )> 0 ) ++count; n >>= 1 ; } return count; } // Function to count pairs of K different bits static long countPairsWithKDiff( int arr[], int n, int k) { long ans = 0 ; // initialize final answer for ( int i = 0 ; i < n- 1 ; ++i) { for ( int j = i + 1 ; j < n; ++j) { int xoredNum = arr[i] ^ arr[j]; // Check for K differ bit if (k == bitCount(xoredNum)) ++ans; } } return ans; } // Driver code public static void main (String[] args) { int k = 2 ; int arr[] = { 2 , 4 , 1 , 3 , 1 }; int n =arr.length; System.out.println( "Total pairs for k = " + k + " are " + countPairsWithKDiff(arr, n, k) + "" ); } } // This code is contributed by shs.. |
Python3
# Python 3 program to count all pairs # with bit difference as k # Utility function to count total # ones in a number def bitCount(n): count = 0 while (n): if (n & 1 ): count + = 1 n >> = 1 return count # Function to count pairs of K different bits def countPairsWithKDiff(arr, n, k): ans = 0 # initialize final answer for i in range ( 0 , n - 1 , 1 ): for j in range (i + 1 , n, 1 ): xoredNum = arr[i] ^ arr[j] # Check for K differ bit if (k = = bitCount(xoredNum)): ans + = 1 return ans # Driver code if __name__ = = '__main__' : k = 2 arr = [ 2 , 4 , 1 , 3 , 1 ] n = len (arr) print ( "Total pairs for k =" , k, "are" , countPairsWithKDiff(arr, n, k)) # This code is contributed by # Sanjit_Prasad |
C#
// C# program to count all pairs // with bit difference as k using System; class GFG { // Utility function to count // total ones in a number static int bitCount( int n) { int count = 0; while (n > 0) { if ((n & 1) > 0) ++count; n >>= 1; } return count; } // Function to count pairs of K different bits static long countPairsWithKDiff( int []arr, int n, int k) { long ans = 0; // initialize final answer for ( int i = 0; i < n-1; ++i) { for ( int j = i + 1; j < n; ++j) { int xoredNum = arr[i] ^ arr[j]; // Check for K differ bit if (k == bitCount(xoredNum)) ++ans; } } return ans; } // Driver code public static void Main () { int k = 2; int []arr = {2, 4, 1, 3, 1}; int n = arr.Length; Console.WriteLine( "Total pairs for k = " + k + " are " + countPairsWithKDiff(arr, n, k) + "" ); } } // This code is contributed by shs.. |
PHP
<?php // PHP program to count all // pairs with bit difference // as k // Utility function to count // total ones in a number function bitCount( $n ) { $count = 0; while ( $n ) { if ( $n & 1) ++ $count ; $n >>= 1; } return $count ; } // Function to count pairs // of K different bits function countPairsWithKDiff( $arr , $n , $k ) { // initialize final answer $ans = 0; for ( $i = 0; $i < $n -1; ++ $i ) { for ( $j = $i + 1; $j < $n ; ++ $j ) { $xoredNum = $arr [ $i ] ^ $arr [ $j ]; // Check for K differ bit if ( $k == bitCount( $xoredNum )) ++ $ans ; } } return $ans ; } // Driver code $k = 2; $arr = array (2, 4, 1, 3, 1); $n = count ( $arr ); echo "Total pairs for k = " , $k , " are " , countPairsWithKDiff( $arr , $n , $k ) , "" ; // This code is contributed by anuj_67. ?> |
Javascript
<script> // JavaScript program to count all pairs with bit difference // as k // Utility function to count total ones in a number function bitCount(n) { let count = 0; while (n>0) { if ((n & 1)>0) ++count; n >>= 1; } return count; } // Function to count pairs of K different bits function countPairsWithKDiff(arr, n, k) { let ans = 0; // initialize final answer for (let i = 0; i < n-1; ++i) { for (let j = i + 1; j < n; ++j) { let xoredNum = arr[i] ^ arr[j]; // Check for K differ bit if (k == bitCount(xoredNum)) ++ans; } } return ans; } // Driver Code let k = 2; let arr = [2, 4, 1, 3, 1]; let n = arr.length; document.write( "Total pairs for k = " + k + " are " + countPairsWithKDiff(arr, n, k) + "" ); </script> |
输出：
Total pairs for k = 2 are 5
时间复杂性： O（N） 2. *log MAX），其中MAX是输入数组中的最大元素。 辅助空间： O（1）
有效的方法
这种方法对于输入数组的元素很小且可能重复很多次的情况是有效的。其思想是从0迭代到max（arr[i]），并对每对（i，j）检查（i^j）中的设置位数，并将其与K进行比较。我们可以使用gcc的内置函数（uu builtin_popcount）或预计算这样的数组，以加快检查速度。如果i^j中的一个数等于K，那么我们将i和j的总数相加。
C++
// Below is C++ approach of finding total k bit // difference pairs #include<bits/stdc++.h> using namespace std; // Function to calculate K bit different pairs in array long long kBitDifferencePairs( int arr[], int n, int k) { // Get the maximum value among all array elements int MAX = *max_element(arr, arr+n); // Set the count array to 0, count[] stores the // total frequency of array elements long long count[MAX+1]; memset (count, 0, sizeof (count)); for ( int i=0; i < n; ++i) ++count[arr[i]]; // Initialize result long long ans = 0; // For 0 bit answer will be total count of same number if (k == 0) { for ( int i = 0; i <= MAX; ++i) ans += (count[i] * (count[i] - 1)) / 2; return ans; } for ( int i = 0; i <= MAX; ++i) { // if count[i] is 0, skip the next loop as it // will not contribute the answer if (!count[i]) continue ; for ( int j = i + 1; j <= MAX; ++j) { //Update answer if k differ bit found if ( __builtin_popcount(i ^ j) == k) ans += count[i] * count[j]; } } return ans; } // Driver code int main() { int k = 2; int arr[] = {2, 4, 1, 3, 1}; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Total pairs for k = " << k << " are = " << kBitDifferencePairs(arr, n, k) << "" ; k = 3; cout << "Total pairs for k = " << k << " are = " << kBitDifferencePairs(arr, n, k) ; return 0; } |
JAVA
// Below is Java approach of finding total k bit // difference pairs import java.util.*; class GFG { // Function to calculate K bit // different pairs in array static long kBitDifferencePairs( int arr[], int n, int k) { // Get the maximum value among all array elements int MAX = Arrays.stream(arr).max().getAsInt(); // Set the count array to 0, // count[] stores the total // frequency of array elements long []count = new long [MAX + 1 ]; Arrays.fill(count, 0 ); for ( int i = 0 ; i < n; ++i) ++count[arr[i]]; // Initialize result long ans = 0 ; // For 0 bit answer will be total // count of same number if (k == 0 ) { for ( int i = 0 ; i <= MAX; ++i) ans += (count[i] * (count[i] - 1 )) / 2 ; return ans; } for ( int i = 0 ; i <= MAX; ++i) { // if count[i] is 0, skip the next loop // as it will not contribute the answer if (count[i] == 0 ) continue ; for ( int j = i + 1 ; j <= MAX; ++j) { // Update answer if k differ bit found if ( Integer.bitCount(i ^ j) == k) ans += count[i] * count[j]; } } return ans; } // Driver code public static void main(String[] args) { int k = 2 ; int arr[] = { 2 , 4 , 1 , 3 , 1 }; int n = arr.length; System.out.println( "Total pairs for k = " + k + " are = " + kBitDifferencePairs(arr, n, k)); k = 3 ; System.out.println( "Total pairs for k = " + k + " are = " + kBitDifferencePairs(arr, n, k)); } } // This code is contributed by Rajput-Ji |
Python3
# Below is Python3 approach of finding # total k bit difference pairs # Function to calculate K bit different # pairs in array def kBitDifferencePairs(arr, n, k): # Get the maximum value among # all array elements MAX = max (arr) # Set the count array to 0, count[] stores # the total frequency of array elements count = [ 0 for i in range ( MAX + 1 )] for i in range (n): count[arr[i]] + = 1 # Initialize result ans = 0 # For 0 bit answer will be total # count of same number if (k = = 0 ): for i in range ( MAX + 1 ): ans + = (count[i] * (count[i] - 1 )) / / 2 return ans for i in range ( MAX + 1 ): # if count[i] is 0, skip the next loop # as it will not contribute the answer if (count[i] = = 0 ): continue for j in range (i + 1 , MAX + 1 ): # Update answer if k differ bit found if ( bin (i ^ j).count( '1' ) = = k): ans + = count[i] * count[j] return ans # Driver code k = 2 arr = [ 2 , 4 , 1 , 3 , 1 ] n = len (arr) print ( "Total pairs for k =" , k, "are" , kBitDifferencePairs(arr, n, k)) k = 3 print ( "Total pairs for k =" , k, "are" , kBitDifferencePairs(arr, n, k)) # This code is contributed by mohit kumar |
C#
// Below is C# approach of finding // total k bit difference pairs using System; using System.Linq; class GFG { // Function to calculate K bit // different pairs in array static long kBitDifferencePairs( int []arr, int n, int k) { // Get the maximum value among // all array elements int MAX = arr.Max(); // Set the count array to 0, // count[] stores the total // frequency of array elements long []count = new long [MAX + 1]; for ( int i = 0; i < n; ++i) ++count[arr[i]]; // Initialize result long ans = 0; // For 0 bit answer will be total // count of same number if (k == 0) { for ( int i = 0; i <= MAX; ++i) ans += (count[i] * (count[i] - 1)) / 2; return ans; } for ( int i = 0; i <= MAX; ++i) { // if count[i] is 0, skip the next loop // as it will not contribute the answer if (count[i] == 0) continue ; for ( int j = i + 1; j <= MAX; ++j) { // Update answer if k differ bit found if (BitCount(i ^ j) == k) ans += count[i] * count[j]; } } return ans; } static int BitCount( int n) { int count = 0; while (n > 0) { count += n & 1; n >>= 1; } return count; } // Driver code public static void Main(String[] args) { int k = 2; int []arr = {2, 4, 1, 3, 1}; int n = arr.Length; Console.WriteLine( "Total pairs for k = " + k + " are = " + kBitDifferencePairs(arr, n, k)); k = 3; Console.WriteLine( "Total pairs for k = " + k + " are = " + kBitDifferencePairs(arr, n, k)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Below is Javascript approach // of finding total k bit // difference pairs // Function to calculate K bit // different pairs in array function kBitDifferencePairs(arr, n, k) { // Get the maximum value among // all array elements let MAX = Math.max(...arr); // Set the count array to 0, count[] stores the // total frequency of array elements let count = new Array(MAX+1).fill(0); for (let i=0; i < n; ++i) ++count[arr[i]]; // Initialize result let ans = 0; // For 0 bit answer will be total // count of same number if (k == 0) { for (let i = 0; i <= MAX; ++i) ans += parseInt((count[i] * (count[i] - 1)) / 2); return ans; } for (let i = 0; i <= MAX; ++i) { // if count[i] is 0, skip // the next loop as it // will not contribute the answer if (!count[i]) continue ; for (let j = i + 1; j <= MAX; ++j) { //Update answer if k differ bit found if ( BitCount(i ^ j) == k) ans += count[i] * count[j]; } } return ans; } function BitCount(n) { let count = 0; while (n > 0) { count += n & 1; n >>= 1; } return count; } // Driver code let k = 2; let arr = [2, 4, 1, 3, 1]; let n = arr.length; document.write( "Total pairs for k = " + k + " are = " + kBitDifferencePairs(arr, n, k) + "<br>" ); k = 3; document.write( "Total pairs for k = " + k + " are = " + kBitDifferencePairs(arr, n, k) + "<br>" ); </script> |
输出：
Total pairs for k = 2 are = 5
时间复杂性： O（最大值） 2. )其中MAX是输入数组中的最大元素。 辅助空间： O（最大值） 本文由 Shubham Bansal .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
