Pairs with Same Parity
MediumPractice library · +20 XPsortingtwo pointerscombinatorics
Given an array of N integers, find the number of pairs (i, j) such that 0 <= i < j < N and the elements at these indices, arr[i] and arr[j], have the same parity (both even or both odd).
Input
The first line contains an integer N. The second line contains N space-separated integers.
Output
Print a single integer, the total count of pairs with the same parity.
Constraints
1 <= N <= 200000; -10^9 <= arr[i] <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 1 2 3 4 5
Output
4
Pairs are (1,3), (1,5), (3,5) [odd-odd] and (2,4) [even-even]. Total 3 + 1 = 4.
Example 2
Input
4 2 4 6 8
Output
6
All numbers are even. Pairs are (2,4), (2,6), (2,8), (4,6), (4,8), (6,8). Total 6.
Hints
Similar problems
- Minimize Maximum Difference in PairsMedium
- Count Unique Element PairsMedium
- Count Pairs with Smaller SumEasy
- Distinct Subarrays with Bounded SumHard
- Sort by Digit SumMedium
- Maximum Sum of Non-Overlapping SegmentsMedium
More topics: Two Pointers problems, Sorting problems, Math and Number Theory problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 2 3 4 5
Example 2 input
4 2 4 6 8