|
This post is completed by 7 users
|
Add to List |
525. Find the number of pairs with odd XOR
Given an array of integers, write a program to find the number of pairs for which the XOR is an odd number.
Example:
Input[] = {3, 2, 1}
Output: 2
Note: 1 XOR 2 = 3 and 2 XOR 3 = 1
Input[] = {3, 6, 9, 4}
Output: 4
Naive Approach: Use nested loops and do the xor for each possible pair from the input array and if xor is an odd number then add it to the result. In the end, print the result.
Time Complexity: O(N^2)
Better Approach: Use XOR property
We know the XOR property, XOR of two elements is odd only when one element is odd and another element is even. Let's see the XOR property below -
even XOR even = even even XOR odd = odd odd XOR even = odd odd XOR odd = even
Iterate the given array and count the number of odd and even elements. Our result would be odd elements * even elements.
Time Complexity: O(N)
Output:
Given Input[] [2, 1, 5, 6, 9, 12, 11, 10, 3] Pairs with odd XOR: 20
Reference: https://math.stackexchange.com/questions/853434/count-pairs-with-odd-xor