给定一个由n个整数组成的数组。找出数组中异或为奇数的对数。 例如：
null
Input : arr[] = { 1, 2, 3 }Output : 2All pairs of array1 ^ 2 = 31 ^ 3 = 22 ^ 3 = 1Input : arr[] = { 1, 2, 3, 4 }Output : 4
天真的方法： 我们可以通过运行两个循环找到异或为奇数的对。若两个数的异或为奇数，则增加对数。
C++
// C++ program to count pairs in array // whose XOR is odd #include <iostream> using namespace std; // A function will return number of pair // whose XOR is odd int countXorPair( int arr[], int n) { // To store count of XOR pair int count = 0; for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) // If XOR is odd increase count if ((arr[i] ^ arr[j]) % 2 == 1) count++; } // Return count return count; } // Driver program to test countXorPair() int main() { int arr[] = { 1, 2, 3 }; int n = sizeof (arr) / sizeof (arr[0]); cout << countXorPair(arr, n); return 0; } |
JAVA
// Java program to count pairs in array whose // XOR is odd public class CountXor { // A function will return number of pair // whose XOR is odd static int countXorPair( int arr[], int n) { // To store count of XOR pair int count = 0 ; for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) // If XOR is odd increase count if ((arr[i] ^ arr[j]) % 2 == 1 ) count++; } // Return count return count; } // Driver program to test countXorPair() public static void main(String[] args) { int arr[] = { 1 , 2 , 3 }; System.out.println(countXorPair(arr, arr.length)); } } |
Python 3
# Python 3 program to count # pairs in array whose XOR is odd # A function will # return number of pair # whose XOR is odd def countXorPair(arr, n): # To store count of XOR pair count = 0 for i in range (n): for j in range (i + 1 , n): # If XOR is odd increase count if ((arr[i] ^ arr[j]) % 2 = = 1 ): count + = 1 # Return count return count # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 ] n = len (arr) print (countXorPair(arr, n)) # This code is contributed # by ChitraNayal |
C#
// C# program to count pairs in // array whose XOR is odd using System; public class CountXor { // A function will return number of pair // whose XOR is odd static int countXorPair( int [] arr, int n) { // To store count of XOR pair int count = 0; for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) // If XOR is odd increase count if ((arr[i] ^ arr[j]) % 2 == 1) count++; } // Return count return count; } // Driver program to test countXorPair() public static void Main() { int [] arr = {1, 2, 3}; Console.WriteLine(countXorPair(arr, arr.Length)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to count // pairs in array // whose XOR is odd // A function will // return number of pair // whose XOR is odd function countXorPair( $arr , $n ) { // To store count // of XOR pair $count = 0; for ( $i = 0; $i < $n ; $i ++) { for ( $j = $i + 1; $j < $n ; $j ++) // If XOR is odd // increase count if (( $arr [ $i ] ^ $arr [ $j ]) % 2 == 1) $count ++; } // Return count return $count ; } // Driver Code $arr = array (1, 2, 3); $n = count ( $arr ); echo countXorPair( $arr , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to count pairs in // array whose XOR is odd // A function will return number of pair // whose XOR is odd function countXorPair(arr, n) { // To store count of XOR pair let count = 0; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) // If XOR is odd increase count if ((arr[i] ^ arr[j]) % 2 == 1) count++; } // Return count return count; } let arr = [1, 2, 3]; document.write(countXorPair(arr, arr.length)); </script> |
输出：
2
时间复杂度：O（n*n） 有效方法： 我们可以观察到：
odd ^ odd = evenodd ^ even = oddeven ^ odd = oddeven ^ even = even
因此，数组中异或为奇数的总对数将等于奇数的计数乘以偶数的计数。
C++
// C++ program to count pairs in array // whose XOR is odd #include <iostream> using namespace std; // A function will return number of pair // whose XOR is odd int countXorPair( int arr[], int n) { // To store count of odd and even // numbers int odd = 0, even = 0; for ( int i = 0; i < n; i++) { // Increase even if number is // even otherwise increase odd if (arr[i] % 2 == 0) even++; else odd++; } // Return number of pairs return odd * even; } // Driver program to test countXorPair() int main() { int arr[] = { 1, 2, 3 }; int n = sizeof (arr) / sizeof (arr[0]); cout << countXorPair(arr, n); return 0; } |
JAVA
// Java program to count pairs in array whose // XOR is odd public class CountXor { // A function will return number of pair // whose XOR is odd static int countXorPair( int arr[], int n) { // To store count of odd and even numbers int odd = 0 , even = 0 ; for ( int i = 0 ; i < n; i++) { // Increase even if number is // even otherwise increase odd if (arr[i] % 2 == 0 ) even++; else odd++; } // Return number of pairs return odd * even; } // Driver program to test countXorPair() public static void main(String[] args) { int arr[] = { 1 , 2 , 3 }; System.out.println(countXorPair(arr, arr.length)); } } |
Python 3
# Python 3 program to count # pairs in array whose XOR is odd # A function will # return number of pair # whose XOR is odd def countXorPair(arr, n): # To store count of # odd and even numbers odd = 0 even = 0 for i in range (n): # Increase even if number is # even otherwise increase odd if arr[i] % 2 = = 0 : even + = 1 else : odd + = 1 # Return number of pairs return odd * even # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 ] n = len (arr) print (countXorPair(arr, n)) # This code is contributed # by ChitraNayal |
C#
// C# program to count pairs in // array whose XOR is odd using System; public class CountXor { // A function will return number of pair // whose XOR is odd static int countXorPair( int [] arr, int n) { // To store count of odd and even numbers int odd = 0, even = 0; for ( int i = 0; i < n; i++) { // Increase even if number is // even otherwise increase odd if (arr[i] % 2 == 0) even++; else odd++; } // Return number of pairs return odd * even; } // Driver program to test countXorPair() public static void Main() { int [] arr = {1, 2, 3}; Console.WriteLine(countXorPair(arr, arr.Length)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to count pairs in array // whose XOR is odd // A function will return number of pair // whose XOR is odd function countXorPair( $arr , $n ) { // To store count of odd // and even numbers $odd = 0; $even = 0; for ( $i = 0; $i < $n ; $i ++) { // Increase even if number is // even otherwise increase odd if ( $arr [ $i ] % 2 == 0) $even ++; else $odd ++; } // Return number of pairs return $odd * $even ; } // Driver Code $arr = array ( 1, 2, 3 ); $n = sizeof( $arr ); echo countXorPair( $arr , $n ); // This code is contributed by Ajit_m ?> |
Javascript
<script> // Javascript program to count pairs in array whose // XOR is odd // A function will return number of pair // whose XOR is odd function countXorPair(arr, n) { // To store count of odd and even numbers let odd = 0, even = 0; for (let i = 0; i < n; i++) { // Increase even if number is // even otherwise increase odd if (arr[i] % 2 == 0) even++; else odd++; } // Return number of pairs return odd * even; } // Driver program to test countXorPair() let arr=[ 1, 2, 3 ]; document.write(countXorPair(arr, arr.length)); // This code is contributed by rag2127 </script> |
输出：
2
时间复杂性： O（n） 本文由 努克洛德 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
