Given an integer array `nums` of length `n`, count the number of index pairs `(i, j)` such that: - `0 <= i < j < n` - `nums[i] * nums[j]` is even - `j - i` is odd Return the total number of special pairs. ### Constraints & Assumptions - A product is even if at least one of the two numbers is even. - `j - i` is odd exactly when `i` and `j` have opposite index parity. - Values may be positive, negative, or zero; only number parity matters. - Return the count, not the pairs. ### Clarifying Questions to Ask - What is the maximum `n`, and can the answer exceed 32-bit integer range? - Are negative values allowed? - Should zero be treated as even? - Is an `O(n)` solution expected? ### Part 1 - Derive The Counting Logic How can you count valid pairs without checking every pair? #### What This Part Should Cover - Index parity condition means pair one even index with one odd index. - Product parity condition means not both numbers are odd. - Count all opposite-index-parity pairs, then subtract pairs where both numbers are odd. ### Part 2 - Implement The Algorithm What variables would you maintain? #### What This Part Should Cover - Counts of even-index positions, odd-index positions, odd values at even indices, and odd values at odd indices. - Formula for result. ### Part 3 - Analyze Complexity And Edge Cases What complexity and edge cases matter? #### What This Part Should Cover - `O(n)` time and `O(1)` space. - Empty or one-element array, zero values, all odd values, all even values, and large counts. ### What a Strong Answer Covers - Uses parity observations instead of brute force. - Correctly handles odd distance and even product conditions. - Avoids double-counting. - Explains why subtracting odd-odd pairs works. ### Follow-up Questions - How would you count pairs where `j - i` is even? - How would the answer change if the product had to be odd? - Can you compute the count in one pass? - What if the input is a stream and indices arrive in order?