CODEWITHSUNDEEP
javaarraysbit-manipulationxor
Ankur Anand
Ankur Anand

Reputation: 3904

Odd Pair of XOR in a large input Arrays

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.

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's working for some value of N but not for large N ~100000.

Sample input: Input 1 Input 2.

Initially I 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 is both the submission of mine 1. Submission of code 1 2. Submission of code 2

Upvotes: 3

Views: 595

Answers (2)

Abhijeet Ashok Muneshwar
Abhijeet Ashok Muneshwar

Reputation: 2508

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

Upvotes: 0

Eran
Eran

Reputation: 393956

In the version that works for all inputs you are using longs to hold the counters :

long oCount = 0, eCount = 0;

In the version that doesn't work for some inputs, you are using ints to hold the counters :

int oddCount = 0, evenCount = 0;

Perhaps you are getting int overflow.

For example, if the number of even numbers is half of all the numbers, both oddCount and evenCount will be 50,000. 50,000*50,000 is 2,500,000,000 which is larger than the max value of int. Therefore oddCount * evenCount will overflow.

Upvotes: 2

Related Questions