Count Even-Product Triplets
Given a list of integers, count how many unordered triplets $(a, b, c)$ -- chosen from distinct positions in the list -- have an even product.
Constraints: - $1 \leq n \leq 10^5$ where $n$ is the length of the list - Elements may be positive, negative, or zero - Triplets are unordered combinations (not permutations)
Examples:
Example 1: nums = [1, 2, 3, 4, 5] Output: 9 Explanation: Total triplets = $\binom{5}{3} = 10$. The only odd triplet is $\{1, 3, 5\}$. So $10 - 1 = 9$.
Example 2: nums = [1, 3, 5, 7] Output: 0 Explanation: All elements are odd, so every product is odd. $\binom{4}{3} - \binom{4}{3} = 0$.
Example 3: nums = [2, 4, 6] Output: 1 Explanation: Only one triplet exists and it contains all even numbers, so product is even.
Hints
- Rather than enumerating cases where the product is even, think about when it is NOT even -- and use complementary counting.
- A product of integers is odd if and only if every factor is odd. So count the odd-element triplets directly.
- Let $m$ be the number of odd elements. The answer is $\binom{n}{3} - \binom{m}{3}$, computable in $O(1)$ after a single pass to count odds.
Worked Solution
How to Think About It: The heuristic is complementary counting: an even product is the messy event (any one of the three factors even), so count its complement -- the product is *odd* iff all three chosen numbers are odd -- and subtract from the total $\binom{n}{3}$. Enumerating the even cases directly (eee, eeo, eoo) is the trap; parity only cares whether an element is odd, so the answer depends on just one number: $m$, the count of odd elements. Only $m$ and $n$ matter -- values, signs, and zeros are irrelevant.
Quick Estimate: Sanity-check on the given example [1,2,3,4,5]. Here $n=5$ and the odd elements are $\{1,3,5\}$, so $m=3$. Total triplets $\binom{5}{3}=\tfrac{5\cdot4\cdot3}{6}=10$; all-odd triplets $\binom{3}{3}=1$ (only $\{1,3,5\}$). Even-product triplets $=10-1=9$. Matches the stated output.
A scale intuition for large $n$: if a fraction $p$ of the list is odd, then $m\approx pn$ and the answer is $\binom{n}{3}-\binom{pn}{3}\approx \binom{n}{3}(1-p^3)$. With half the list odd ($p=\tfrac12$), a fraction $1-\tfrac18=\tfrac78\approx 88\%$ of all triplets have an even product -- so for a random list you expect the answer to be roughly $\tfrac78\binom{n}{3}$, a fast plausibility check on any computed value.
Algorithm: One pass to count odd elements $m$; then $\binom{n}{3}-\binom{m}{3}$ in $O(1)$.
Code: ```python def count_even_triplets(nums): n = len(nums) m = sum(1 for x in nums if x % 2 != 0) # count of odd elements total = n * (n - 1) * (n - 2) // 6 odd_triplets = m * (m - 1) * (m - 2) // 6 return total - odd_triplets ```
Formal Solution: A product of integers is odd iff every factor is odd (a single even factor injects a factor of 2). Among $\binom{n}{3}$ unordered triplets, the odd-product ones are precisely those drawn entirely from the $m$ odd elements: $\binom{m}{3}$. All remaining triplets contain at least one even element and hence have an even product. Therefore
$$\#\{\text{even-product triplets}\} = \binom{n}{3} - \binom{m}{3},$$
with the convention $\binom{t}{3}=0$ for $t<3$. Zeros and negatives are handled automatically: zero is even, negatives keep their parity, so they only affect $m$ through the $x\bmod 2$ test.
Complexity: $O(n)$ time, $O(1)$ space.
Answer: $\displaystyle \binom{n}{3}-\binom{m}{3}$ where $m$ is the number of odd elements; $O(n)$ time. (Example [1,2,3,4,5]: $10-1=9$.)
Intuition
Complementary counting is one of the most powerful tools in combinatorics precisely because it converts a multi-case problem into a single easy case. Here, 'even product' has three sub-cases involving at least one even number, while 'odd product' has exactly one sub-case: all three numbers are odd. The hard count becomes trivial once you flip to the complement.
This trick appears constantly in probability and combinatorics: instead of computing $P(\text{at least one success})$ directly, compute $1 - P(\text{no successes})$. The structure is identical -- you are always looking for the one 'pure' case that is easy to count, then subtracting.