Count Indices With Opposite Parity - Solution & Explanation

Problem Overview: You receive an integer array and need to count positions where the index and the value at that index have opposite parity. In other words, if the index is even, the value should be odd, and if the index is odd, the value should be even. The task is simply to scan the array and count how many positions violate the same-parity condition.

Approach 1: Direct Parity Check (O(n) time, O(1) space)

Iterate through the array once and compare the parity of the index with the parity of the value. You can compute parity using % 2 or bitwise operations like & 1. If index % 2 differs from nums[i] % 2, the pair has opposite parity and contributes to the count. This approach uses a simple linear scan and constant memory, making it the optimal solution for this problem. It falls under basic arrays traversal with a small amount of math logic.

The key insight is that parity comparison is constant-time. You don't need extra data structures or preprocessing. Each element is inspected exactly once, and the answer increments whenever the parity mismatch condition holds.

Approach 2: Bitwise Parity Comparison (O(n) time, O(1) space)

This approach performs the same logic but uses bit operations instead of modulus. The least significant bit determines parity: x & 1 returns 0 for even numbers and 1 for odd numbers. During iteration, compute (i & 1) and (nums[i] & 1). If the two bits differ, the index and value have opposite parity. Bitwise checks are slightly faster than modulus operations and commonly appear in low-level optimizations or competitive programming. The logic fits naturally into problems involving bit manipulation.

Although both approaches have identical asymptotic complexity, the bitwise version highlights how parity can be extracted directly from the binary representation of numbers. In practice, the performance difference is negligible for typical constraints.

Approach 3: Two-Pass Counting Strategy (O(n) time, O(1) space)

Another way to think about the problem is to track mismatches by category. During traversal, count how many even indices contain odd values and how many odd indices contain even values. Each mismatch category contributes directly to the final answer. This version doesn't improve complexity but sometimes helps when extending the problem—for example, if you later need to report which indices violate parity or perform corrections.

Recommended for interviews: The single-pass parity comparison is what interviewers expect. It shows you recognize that parity is a constant-time property and that the problem reduces to a simple array scan. Mentioning the bitwise optimization demonstrates awareness of low-level parity checks, while the brute reasoning confirms you understand the condition clearly.