Count pairs with odd XOR

Question

Given an array A1,A2...AN. We have to tell how many pairs (i, j) exist such that 1 ≤ i < j ≤ N and Ai XOR Aj is odd.

Example : If N=3 and array is [1 2 3] then here answer is 2 as 1 XOR 2 is 3 and 2 XOR 3 is 1. So, 2 valid pairs.

Problem is that N can be upto 10^5.So how to do it. Please help

Answer 1

Hint: Note that $A_i \text{ XOR } A_j$ is odd precisely when $A_i$ and $A_j$ have opposite parity. So count the odd and even numbers in your array... This gives you an $O(n)$ algorithm instead of $O(n^2)$

Answer 2

XOR of even and odd number is odd.

Hence in a given array [A1,A2...AN], find total number of even elements and total number of odd elements.

As we've to find number of all pairs having odd XOR, then answer is multiplication of total odd elements and total even elements.

Below is my solution in PHP.

<?php
/**
 * Created by PhpStorm.
 * User: abhijeet
 * Date: 14/05/16
 * Time: 3:51 PM
 * https://www.hackerearth.com/problem/algorithm/sherlock-and-xor/description/
Input and Output
First line T, the number of test cases. Each test case: first line N, followed by N integers in next line. For each testcase, print the required answer in one line.
2
3
1 2 3
4
1 2 3 4
 */
fscanf(STDIN, "%d\n", $n);
while($n--) {
    fscanf(STDIN, "%d\n", $len);
    $a_temp = rtrim(fgets(STDIN), "\n\r");
    $a = explode(" ", $a_temp);
    array_walk($a, 'intval');
    $odd = 0;
    $even = 0;
    for($i=0; $i<$len; $i++) {
        if($a[$i]%2) {
            $odd++;
        } else{
            $even++;
        }
    }
    echo ($odd * $even) . "\n";
}
?>