3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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)$

$\endgroup$
1
  • $\begingroup$ Any boundary cases to be taken care off? $\endgroup$ – user157452 Jul 1 '14 at 17:00
1
$\begingroup$

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";
}
?>
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.