Sherlock and XOR
Practice
3.8 (63 votes)
Approved
Basic programming
Easy
Math
Open
Problem
84% Success 31383 Attempts 20 Points 2s Time Limit 256MB Memory 1024 KB Max Code
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 ≤ 105
0 ≤ Ai ≤ 109
Sample Input
2 3 1 2 3 4 1 2 3 4
Sample Output
2 4
Explanation
For first testcase: 1 XOR 2 is 3 and 2 XOR 3 is 1. So, 2 valid pairs. For second testcase: 1 XOR 2 is 3 and 2 XOR 3 is 1 and 1 XOR 4 is 5 and 3 XOR 4 is 7. So, 4 valid pairs.
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Submissions
Please login to view your submissions
Similar Problems
Points:20
131 votes
Tags:
Bit manipulationEasyOpenSorting
Points:20
15 votes
Tags:
SortingBasic ProgrammingBit ManipulationMerge SortBasics of Bit ManipulationAlgorithmsBit manipulationBitmask
Points:20
35 votes
Tags:
Ad-HocApprovedBasic ProgrammingEasyOpen
Editorial
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor