This post is completed by 1 user

Add to List 
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*(n1)/2
 So our final result = x*(x1)/2 + y*(y1)/2
Time Complexity: O(N)
Output:
Given Input[] [2, 1, 5, 6, 9, 12, 11, 10, 3] Pairs with even XOR: 16