Maximum Double Pairing: Find the Maximum Number of Disjoint Pairs with Sum Divisible by 2

Question

## Problem

Given an array of integers, find the maximum number of disjoint pairs `(i, j)` (with `i < j`) such that `arr[i] + arr[j]` is even (divisible by 2). Each element can belong to at most one pair.

```python
def max_even_pairs(arr: list[int]) -> int:
    pass
```

**Example:**
```
arr = [1, 2, 3, 4, 5, 6]
# even+even: (2,4),(4,6),(2,6) -- can pick 2 disjoint even pairs
# odd+odd:  (1,3),(3,5),(1,5) -- can pick 2 disjoint odd pairs? No only 3 odds: floor(3/2)=1... wait 3 odds -> 1 pair
# total: floor(3/2) + floor(3/2) = 1 + 1 = ... let me recount: odds=[1,3,5] evens=[2,4,6]
# max pairs = floor(3/2) + floor(3/2) = 1+1=2? No: floor(3/2)=1, floor(3/2)=1 -> 2
-> 3   # (2,4),(2 used), wait: 3 odds give 1 pair, 3 evens give 1 pair -> 2 total
# Correction: [1,2,3,4,5,6]: 3 odds, 3 evens -> 1+1=2 pairs
-> 2
```

## Follow-ups

1. Prove that the answer is always `floor(odd_count / 2) + floor(even_count / 2)`. Why is a greedy approach optimal here?
2. How does this change if you want pairs whose sum is divisible by `k` (not just 2)?
3. What if the array can contain negative numbers? Does the parity argument still hold?
4. How would you enumerate all such pairs (not just count them) efficiently?

Maximum Double Pairing: Find the Maximum Number of Disjoint Pairs with Sum Divisible by 2

Question Details

Full Details

Topics

More from Uber