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
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
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
29 votes
Tags:
BitmaskBasic ProgrammingBit ManipulationBasics of Bit ManipulationGreedy AlgorithmsBit manipulation
Points:30
150 votes
Tags:
ReadyBrute-force searchEasy-MediumApprovedBreadth-first search
Points:20
196 votes
Tags:
EasyHash MapsOpen
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
Results
Custom Input
Run your code to see the output