This post is completed by 1 user

  • 0
 Add to List
Beginner

492. Find the number of pairs with even XOR

Given an array of integers, write a program to find the number of pairs for which the XOR is an even number.

Example:

Input[] = {3, 2, 1}
Output: 1
Note: 1 XOR 3 = 2

Input[] = {3, 6, 9, 4}
Output: 2

Naive Approach: Use nested loops and do the xor for each possible pair from the input array and if xor is an even 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 even only when either both the elements are even or both the elements are odd. 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 elements (let's call it x) and even elements (let's call it y). Now we will calculate for odd and even elements separately and add them for the final result. 
  • Problem is now reduced to - number of ways to choose 2 elements out of n, which is nC2 = n*(n-1)/2
  • So our final result = x*(x-1)/2 + y*(y-1)/2

Time Complexity: O(N)

Output:

Given Input[] [2, 1, 5, 6, 9, 12, 11, 10, 3]
Pairs with even XOR: 16

Related Problems: