Given an array of n integers. Find out number of pairs in array whose XOR is odd.
Examples :
Input : arr[] = { 1, 2, 3 }
Output : 2
All pairs of array
1 ^ 2 = 3
1 ^ 3 = 2
2 ^ 3 = 1
Input : arr[] = { 1, 2, 3, 4 }
Output : 4
Naive Approach: We can find pairs whose XOR is odd by running two loops. If XOR of two number is odd increase count of pairs.
Implementation:
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> |
Output
2
Time Complexity : O(n*n)
Space Complexity – O(1)
Efficient Approach: We can observe that:
odd ^ odd = even odd ^ even = odd even ^ odd = odd even ^ even = even
Therefore total pairs in array whose XOR is odd will be equal to count of odd numbers multiplied by count of even numbers.
Implementation:
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> |
Output
2
Time Complexity : O(n)
Space Complexity : O(1)
This article is contributed by nuclode. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
