Count Indices With Opposite Parity solution and explanation
6 more videos on this problem
Count Indices with Opposite Parity | LeetCode 3917 | Weekly Contest 500 | Java | Developer CoderDeveloper Coder · 8:50 · 111 views
Weekly Contest 500 | Count Indices With Opposite Parity | Q1 | Leetcode 3917 | ArrayPragya Gupta · 18:55 · 85 views
LeetCode Problem 3917 | Count Indices With Opposite ParityRepovive TV · 5:06 · 55 views
Count Indices With Opposite Parity | O(n) TC | Leetcode weekly contest 500 | #3917UMANG AGRAWAL · 8:14 · 50 views
Count Indices With Opposite Parity | Leetcode 3917 | Explanation With Code | Javacodewithsitaram · 11:38 · 38 views
Leetcode 3917 Count Indices With Opposite Parity | Weekly Contest 500 | Telugu | #leetcode #telugucodewarriortelugu · 3:17 · 18 views
LeetCode 3917 in 0ms 🚀 | Count Indices With Opposite Parity | Easy C++ SolutionRishab Chandgothia · 6:40 · 3 views
The problem
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, andnums[i]andnums[j]have different parity (one is even and the other is odd).
Return an integer array answer of length n, where answer[i] is the score of index i.
Example 1:
Input: nums = [1,2,3,4]
Output: [2,1,1,0]
Explanation:
nums[0] = 1, which is odd. Thus, the indicesj = 1andj = 3satisfy the conditions, so the score of index 0 is 2.nums[1] = 2, which is even. Thus, the indexj = 2satisfies the conditions, so the score of index 1 is 1.nums[2] = 3, which is odd. Thus, the indexj = 3satisfies the conditions, so the score of index 2 is 1.nums[3] = 4, which is even. Thus, no index satisfies the conditions, so the score of index 3 is 0.
Thus, the answer = [2, 1, 1, 0].
Example 2:
Input: nums = [1]
Output: [0]
Explanation:
There is only one element in nums. Thus, the score of index 0 is 0.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
Approach overview
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.
Solution
We first count the number of even and odd elements in the array nums, denoted as cnt[0] and cnt[1] respectively.
Then, we traverse the array nums from left to right. For index i, we first decrement cnt[nums[i] bmod 2] by 1, then assign cnt[nums[i] bmod 2 \oplus 1] to ans[i].
After the traversal, return the answer array ans.
The time complexity is O(n), where n is the length of the array nums. Ignoring the space complexity of the answer array, the space complexity is O(1).
class Solution:
def countOppositeParity(self, nums: list[int]) -> list[int]:
cnt = [0, 0]
for x in nums:
cnt[x & 1] += 1
ans = [0] * len(nums)
for i, x in enumerate(nums):
cnt[x & 1] -= 1
ans[i] = cnt[x & 1 ^ 1]
return ansclass Solution {
public int[] countOppositeParity(int[] nums) {
int[] cnt = new int[2];
for (int x : nums) {
cnt[x & 1]++;
}
int n = nums.length;
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
cnt[nums[i] & 1]--;
ans[i] = cnt[nums[i] & 1 ^ 1];
}
return ans;
}
}class Solution {
public:
vector<int> countOppositeParity(vector<int>& nums) {
int cnt[2] = {0, 0};
for (int x : nums) {
cnt[x & 1]++;
}
int n = nums.size();
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
cnt[nums[i] & 1]--;
ans[i] = cnt[(nums[i] & 1) ^ 1];
}
return ans;
}
};function countOppositeParity(nums: number[]): number[] {
const cnt = Array<number>(2).fill(0);
for (const x of nums) {
++cnt[x & 1];
}
const n = nums.length;
const ans = Array<number>(n).fill(0);
for (let i = 0; i < n; ++i) {
--cnt[nums[i] & 1];
ans[i] = cnt[(nums[i] & 1) ^ 1];
}
return ans;
}func countOppositeParity(nums []int) []int {
cnt := [2]int{}
for _, x := range nums {
cnt[x&1]++
}
n := len(nums)
ans := make([]int, n)
for i, x := range nums {
cnt[x&1]--
ans[i] = cnt[x&1^1]
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Parity Check (modulo) | O(n) | O(1) | General case; simplest and most readable implementation |
| Bitwise Parity Comparison | O(n) | O(1) | When using low-level optimizations or competitive programming patterns |
| Two-Pass Mismatch Counting | O(n) | O(1) | Useful if extending the problem to track mismatch categories |
Frequently asked questions
Is Count Indices With Opposite Parity easy or hard?
Count Indices With Opposite Parity is considered an easy problem. It mainly tests whether you understand parity (even vs odd numbers) and can perform a linear array scan with a simple condition check.
Count Indices With Opposite Parity Python/Java solution
Both Python and Java implementations follow the same logic: iterate through the array and compare index parity with value parity. If they differ, increment a counter. The algorithm runs in O(n) time and uses O(1) space regardless of language.
How to solve Count Indices With Opposite Parity in O(n)?
Traverse the array from index 0 to n-1. For each position, compute the parity of the index and the element. If (i % 2) != (nums[i] % 2), the index and value have opposite parity, so increase the count. This linear scan guarantees O(n) time and constant memory usage.
What is the best approach for Count Indices With Opposite Parity?
The best approach is a single-pass parity comparison. Iterate through the array and compare the parity of the index with the parity of the element using i % 2 and nums[i] % 2 (or bitwise checks). If the two differ, increment the counter. This solution runs in O(n) time with O(1) extra space.
Is Count Indices With Opposite Parity asked at Google/Amazon/Meta?
Problems involving parity checks and simple array traversal frequently appear in coding interviews at large tech companies. While this exact question may vary by platform, the pattern—scanning an array and applying a condition per index—is a common interview exercise used by companies like Amazon, Google, and Meta.
What data structure is used in Count Indices With Opposite Parity?
The problem only requires a basic array traversal. No additional data structures like hash maps, stacks, or heaps are needed. A single integer counter tracks how many positions satisfy the opposite parity condition.
What is the time complexity of Count Indices With Opposite Parity?
The optimal solution runs in O(n) time because the array is scanned exactly once. Each step performs constant-time parity checks using modulo or bitwise operations. The space complexity is O(1) since only a counter variable is required.