This post is completed by 7 users

  • 2
 Add to List
Beginner

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

Related Problems: