Welcome to Subscribe On Youtube

3917. Count Indices With Opposite Parity

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).

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 indices j = 1 and j = 3 satisfy the conditions, so the score of index 0 is 2.
  • nums[1] = 2, which is even. Thus, the index j = 2 satisfies the conditions, so the score of index 1 is 1.
  • nums[2] = 3, which is odd. Thus, the index j = 3 satisfies 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 <= 100
  • 1 <= nums[i] <= 100

Solutions

Solution 1: Counting

We first count the number of even and odd elements in the array $\textit{nums}$, denoted as $cnt[0]$ and $cnt[1]$ respectively.

Then, we traverse the array $\textit{nums}$ from left to right. For index $i$, we first decrement $cnt[\textit{nums}[i] \bmod 2]$ by 1, then assign $cnt[\textit{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 $\textit{nums}$. Ignoring the space complexity of the answer array, the space complexity is $O(1)$.

  • class 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;
    }
};


  • 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 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
}


  • 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;
}

All Problems

All Solutions