3917. Count Indices With Opposite Parity

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n.

The score of an index i is defined as the number of indices j such that:

i < j < n, and
nums[i] and nums[j] have different parity (one is even and the other is odd).

In other words, for each index i, you need to count how many elements that appear after index i have a parity opposite to that of nums[i]. If nums[i] is even, you count the odd elements to its right; if nums[i] is odd, you count the even elements to its right.

Return an integer array answer of length n, where answer[i] is the score of index i.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Following the described procedure step by step produces the solution.

Open in Flowchart

Intuition

For each index i, the score is the number of elements after it that have the opposite parity. A naive approach would be to check every pair (i, j), but that takes O(n^2) time.

The key observation is that we only care about the parity of each number, not its exact value. So instead of comparing each pair, we can simply keep track of how many even numbers and how many odd numbers exist to the right of the current index.

To do this efficiently, we first count the total number of even and odd elements in the whole array, storing them in cnt[0] (even count) and cnt[1] (odd count).

Then, as we walk through the array from left to right, the elements "to the right" of index i are exactly the elements we have not yet processed. So before recording the answer for index i, we remove the current element from the count by decrementing cnt[nums[i] % 2]. After this step, cnt reflects only the elements strictly after i.

Since we want the count of the opposite parity, we look up cnt at the flipped parity. If nums[i] is even (parity 0), we want the odd count at index 1; if it is odd (parity 1), we want the even count at index 0. The bitwise XOR nums[i] & 1 ^ 1 neatly flips the parity to give us the right index.

This way, we compute every answer in a single pass with O(n) time and O(1) extra space (besides the output array).

Solution Approach

Solution 1: Counting

We first count the number of even and odd elements in the array nums, denoted as cnt[0] and cnt[1] respectively. We do this by iterating over each element x and incrementing cnt[x & 1], where x & 1 gives 0 for even numbers and 1 for odd numbers.

Then, we traverse the array nums from left to right. For index i, we first decrement cnt[nums[i] & 1] by 1, which removes the current element from the count so that cnt now reflects only the elements strictly to the right of i. Next, we assign cnt[nums[i] & 1 ^ 1] to ans[i]. The expression nums[i] & 1 ^ 1 flips the parity bit, so we look up the count of elements with the opposite parity.

After the traversal, we return the answer array ans.

The time complexity is O(n), where n is the length of the array nums, since we make two passes over the array. The space complexity is O(1) for the counting array (excluding the output array ans).

Example Walkthrough

Let's trace through the solution approach using a small example:

nums = [3, 2, 5, 4]

Here, n = 4. The parities are:

3 → odd (parity 1)
2 → even (parity 0)
5 → odd (parity 1)
4 → even (parity 0)

Step 1: Count all even and odd elements.

We iterate over nums and increment cnt[x & 1]:

3 & 1 = 1 → cnt[1] += 1
2 & 1 = 0 → cnt[0] += 1
5 & 1 = 1 → cnt[1] += 1
4 & 1 = 0 → cnt[0] += 1

After this pass: cnt = [2, 2] (2 even numbers, 2 odd numbers).

Step 2: Traverse from left to right, building ans.

For each index i, we first decrement cnt[nums[i] & 1] to exclude the current element, then read the opposite parity count at cnt[nums[i] & 1 ^ 1].

`i`	`nums[i]`	parity `nums[i]&1`	After decrement `cnt`	opposite index `&1^1`	`ans[i]`
0	3	1	`[2, 1]`	0	`cnt[0] = 2`
1	2	0	`[1, 1]`	1	`cnt[1] = 1`
2	5	1	`[1, 0]`	0	`cnt[0] = 1`
3	4	0	`[0, 0]`	1	`cnt[1] = 0`

Let's verify each result manually:

i = 0 (nums[0] = 3, odd): elements after it are 2, 5, 4. Even ones are 2 and 4 → count 2. ✓
i = 1 (nums[1] = 2, even): elements after it are 5, 4. Odd ones are 5 → count 1. ✓
i = 2 (nums[2] = 5, odd): elements after it are 4. Even ones are 4 → count 1. ✓
i = 3 (nums[3] = 4, even): no elements after it → count 0. ✓

Final answer:

ans = [2, 1, 1, 0]

This walkthrough shows how decrementing the count before reading it keeps cnt aligned with "elements strictly to the right of i", and how the XOR trick (& 1 ^ 1) cleanly flips the parity bit so we always read the opposite-parity count in a single O(n) pass.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def countOppositeParity(self, nums: List[int]) -> List[int]:
6        # parity_count[0]: number of even values, parity_count[1]: number of odd values
7        parity_count = [0, 0]
8        for value in nums:
9            parity_count[value & 1] += 1
10
11        result = [0] * len(nums)
12        for index, value in enumerate(nums):
13            # Remove the current element from its own parity bucket
14            parity_count[value & 1] -= 1
15            # value & 1 ^ 1 flips the parity bit, so we read the opposite-parity count
16            result[index] = parity_count[(value & 1) ^ 1]
17
18        return result
19

1class Solution {
2    /**
3     * For each element in the array, counts how many other elements have the
4     * opposite parity (odd vs. even).
5     *
6     * @param nums the input array of integers
7     * @return an array where ans[i] is the number of elements (excluding index i)
8     *         whose parity is opposite to nums[i]
9     */
10    public int[] countOppositeParity(int[] nums) {
11        // parityCount[0] = total count of even numbers
12        // parityCount[1] = total count of odd numbers
13        int[] parityCount = new int[2];
14        for (int value : nums) {
15            // value & 1 yields 0 for even, 1 for odd
16            parityCount[value & 1]++;
17        }
18
19        int length = nums.length;
20        int[] ans = new int[length];
21
22        for (int i = 0; i < length; i++) {
23            int parity = nums[i] & 1;
24
25            // Exclude the current element from the running totals
26            parityCount[parity]--;
27
28            // Look up the count of elements with the opposite parity.
29            // parity ^ 1 flips 0 -> 1 and 1 -> 0.
30            ans[i] = parityCount[parity ^ 1];
31        }
32
33        return ans;
34    }
35}
36

1class Solution {
2public:
3    vector<int> countOppositeParity(vector<int>& nums) {
4        // parityCount[0] -> number of even values, parityCount[1] -> number of odd values
5        int parityCount[2] = {0, 0};
6
7        // First pass: tally how many numbers are even and how many are odd
8        for (int value : nums) {
9            parityCount[value & 1]++;
10        }
11
12        int n = static_cast<int>(nums.size());
13        vector<int> answer(n);
14
15        // Second pass: for each index, count elements (excluding current) with opposite parity
16        for (int i = 0; i < n; ++i) {
17            int currentParity = nums[i] & 1;
18
19            // Remove the current element from the running counts so it is not counted
20            parityCount[currentParity]--;
21
22            // Elements with opposite parity are those whose parity bit is flipped
23            int oppositeParity = currentParity ^ 1;
24            answer[i] = parityCount[oppositeParity];
25
26            // Restore the count so subsequent iterations see the full remaining set
27            // (Note: the original logic intends "remaining after this index",
28            //  so we keep it decremented to preserve the original behavior.)
29            // parityCount[currentParity]++; // intentionally NOT restored to match original logic
30        }
31
32        return answer;
33    }
34};
35

1function countOppositeParity(nums: number[]): number[] {
2    // count[0] = number of even values, count[1] = number of odd values
3    const count = Array<number>(2).fill(0);
4    for (const value of nums) {
5        // value & 1 yields 0 for even and 1 for odd
6        ++count[value & 1];
7    }
8
9    const n = nums.length;
10    const ans = Array<number>(n).fill(0);
11
12    for (let i = 0; i < n; ++i) {
13        // Remove the current element from the parity counts,
14        // so the remaining counts represent the other elements
15        --count[nums[i] & 1];
16        // For the current element, take the count of the opposite parity.
17        // (parity ^ 1) flips 0 <-> 1 to reference the opposite bucket
18        ans[i] = count[(nums[i] & 1) ^ 1];
19    }
20
21    return ans;
22}
23

Time and Space Complexity

Time complexity: O(n), where n is the length of the array nums. The code iterates through the array twice: the first loop counts the number of even and odd elements, and the second loop computes the answer for each index. Both loops run in linear time, so the overall time complexity is O(n).
Space complexity: O(1). The algorithm only uses a fixed-size auxiliary array cnt of length 2 to store the counts of even and odd numbers, regardless of the input size. Ignoring the space complexity of the answer array ans, the extra space used is constant.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Operator Precedence Confusion with `&` and `^`

The most common mistake when writing this solution is misunderstanding the operator precedence between the bitwise AND (&) and bitwise XOR (^) operators. Many developers assume & binds tighter than ^ in a way that matches their intent, but mistakes often arise when parentheses are omitted in the wrong place.

In Python, the precedence order is: & (higher) → ^ → | (lower). So the expression:

value & 1 ^ 1

is actually evaluated as:

(value & 1) ^ 1

This happens to be correct for our purpose, but the danger appears when someone tries to "simplify" or rewrite it. For example, a developer might mistakenly write:

result[index] = parity_count[value & (1 ^ 1)]  # WRONG!

Here 1 ^ 1 evaluates to 0, so the expression becomes value & 0, which is always 0. This would always read parity_count[0] (the even count), producing incorrect results for odd elements.

Solution: Always use explicit parentheses to make the intent unambiguous:

opposite_parity = (value & 1) ^ 1
result[index] = parity_count[opposite_parity]

Pitfall 2: Forgetting to Decrement Before Reading

A subtle but critical pitfall is the order of the decrement and the read operations. The current element at index i must be excluded from the count because the score only considers indices j where i < j. If you read the opposite-parity count before decrementing, the count would still be correct for the opposite parity (since the current element shares the same parity, not the opposite one). However, the bug becomes harmful if you accidentally decrement the opposite bucket or reorder the logic incorrectly.

Consider this incorrect variation:

for index, value in enumerate(nums):
    result[index] = parity_count[(value & 1) ^ 1]
    parity_count[value & 1] -= 1  # decrement happens after read

In this specific case the result is still correct because decrementing the same-parity bucket doesn't affect the opposite-parity read. The real danger is when a developer "optimizes" by decrementing the opposite bucket or conflates the two indices.

Solution: Keep the logic explicit and consistent—decrement the current element's own parity bucket first, then read the opposite parity bucket. This makes the invariant clear: after the decrement, parity_count reflects only elements strictly to the right of i.

parity_count[value & 1] -= 1           # exclude current element
result[index] = parity_count[(value & 1) ^ 1]  # read opposite parity

Pitfall 3: Using Negative Numbers and `& 1`

When the array contains negative integers, some developers worry that value & 1 might behave unexpectedly. In languages with sign-magnitude or one's complement representations this could be an issue, but in Python (which uses arbitrary-precision two's complement), value & 1 correctly returns 1 for odd negatives (e.g., -3 & 1 == 1) and 0 for even negatives (e.g., -4 & 1 == 0).

A common mistake is replacing the bit check with value % 2, which in Python returns 1 for odd values but can confuse those coming from C/C++/Java, where -3 % 2 == -1. Using such a result directly as a list index would raise an IndexError or read the wrong bucket.

Solution: Prefer value & 1 for parity checks, as it reliably yields 0 or 1 regardless of sign:

parity_bit = value & 1  # always 0 or 1, safe as an index

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of these pictures shows the visit order of a depth-first search?

I don't know