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

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 .

最初我是这样写的，没有任何功能，主类中的所有东西都是这样的，并且它通过了所有测试

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

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

long oCount = 0, eCount = 0;

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

int oddCount = 0, evenCount = 0;

也许您遇到了 int 溢出。

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