Odd XOR pair in large input arrays
You are given an array A1, A2 ... AN. You have to say how many pairs (i, j) there are such that 1 ≤ i <j ≤ N and Ai XOR Aj is odd.
Input and Output
First line T, number of checks. each testcase: first line N followed by N integers on the next line. For each testcase, print the required answer on one line.Limitations
1 ≤ T ≤ 10 1 ≤ N ≤ 10^5 0 ≤ Ai ≤ 10^9
.
My code:
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int totalTestCaseT = Integer.parseInt(reader.readLine());
StringBuilder outputOddCount = new StringBuilder();
for (int i = 0; i < totalTestCaseT; i++) {
int lengthOinputT = Integer.parseInt(reader.readLine());
String input = reader.readLine().trim();
long oddXorCount = getOddXorCount(input, lengthOinputT);
outputOddCount.append(oddXorCount);
outputOddCount.append("\n");
}
System.out.println(outputOddCount);
}
private static long getOddXorCount(String input, int lengthOinputT) {
String[] inputArray = input.split(" ");
int oddCount = 0, evenCount = 0;
for (int i = 0; i < lengthOinputT; i++) {
String lastDigit = String.valueOf((inputArray[i]
.charAt(inputArray[i].length() - 1)));
int unitDigit = Integer.parseInt(lastDigit);
if ((unitDigit & 1) == 1) {
oddCount++;
} else
evenCount++;
}
return oddCount * evenCount;
}
It works for some value of N, but not for large N ~ 100000.
Input example: Input 1 Input 2 .
I originally wrote it without any function with everything in the main class like this and it passed all tests
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
int tCases = Integer.parseInt(line);
for (int i = 0; i < tCases; i++) {
long oCount = 0, eCount = 0;
int N = Integer.parseInt(br.readLine());
String[] A = br.readLine().toString().split(" ");
for (int j = 0; j < N; j++) {
int unitDigit = Integer
.parseInt((A[j].charAt(A[j].length() - 1)) + "");
if (unitDigit % 2 == 0)
eCount++;
else
oCount++;
}
System.out.println(eCount * oCount);
}
Here's a view of mine 1. Code view 1 2. Code view 2
source to share
In the version that works for all inputs, you use long
to store counters:
long oCount = 0, eCount = 0;
In a version that doesn't work for some inputs, you use int
to store counters:
int oddCount = 0, evenCount = 0;
You may be getting an overflow int
.
For example, if the number of even numbers is half of all numbers, then both oddCount and evenCount will be 50,000. 50,000 * 50,000 is 2,500,000,000, which is greater than the maximum int value. Therefore it oddCount * evenCount
will overflow.
source to share
XOR odd and even number is odd.
Therefore, in the given array [A1, A2 ... AN], find the total number of even elements and the total number of odd elements.
How are we supposed to find the number of all pairs with an odd XOR, then the answer will be the multiplication of the total odd elements and the 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";
}
?>
source to share