大输入数组中的奇数异或对

Question

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

Input and Output First line T, the number of testcases. Each testcase: first line N, followed by N integers in next line. For each testcase, print the required answer in one line.

Constraints 1 ≤ T ≤ 10 1 ≤ N ≤ 10^5 0 ≤ Ai ≤ 10^9.

我的代码：

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;
    }

它适用于 N 的某些值，但不适用于大 N ~100000。

示例输入：Input 1 Input 2.

最初我是这样写的，没有任何功能，主要是class，它通过了所有测试

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);
    }

这是我的提交 1. Submission of code 1 2. Submission of code 2

Answer 1

在适用于所有输入的版本中，您使用 longs 来保存计数器：

long oCount = 0, eCount = 0;

在对某些输入不起作用的版本中，您正在使用 ints 来保存计数器：

int oddCount = 0, evenCount = 0;

也许您 int 溢出了。

例如，如果偶数的个数是所有数的一半，则oddCount和evenCount都是50,000。 50,000*50,000 是 2,500,000,000，大于 int 的最大值。因此 oddCount * evenCount 会溢出。

Answer 2

偶数和奇数异或为奇数

因此在给定的数组[A1,A2...AN]中，找出偶数元素的总数和奇数元素的总数。

因为我们要找到具有奇异或的所有对的数量，所以答案是奇数元素总数与偶数元素总数的乘积。

下面是我在 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";
}
?>

大输入数组中的奇数异或对

Odd Pair of XOR in a large input Arrays

java

arrays

bit-manipulation

xor