# LC 3152. Special Array II

### [Problem link](https://leetcode.com/problems/special-array-ii/)

###### tags: `leedcode` `medium` `c++`

An array is considered **special** if every pair of its adjacent elements contains two numbers with different parity.

You are given an array of integer <code>nums</code> and a 2D integer matrix <code>queries</code>, where for <code>queries[i] = [from_i, to_i]</code> your task is to check that subarray <code>nums[from_i..to_i]</code> is **special** or not.

Return an array of booleans <code>answer</code> such that <code>answer[i]</code> is <code>true</code> if <code>nums[from_i..to_i]</code> is special.

**Example 1:**

Input: nums = [3,4,1,2,6], queries = [[0,4]]

Output: [false]

Explanation:

The subarray is <code>[3,4,1,2,6]</code>. 2 and 6 are both even.

**Example 2:**

Input: nums = [4,3,1,6], queries = [[0,2],[2,3]]

Output: [false,true]

Explanation:

- The subarray is <code>[4,3,1]</code>. 3 and 1 are both odd. So the answer to this query is <code>false</code>.
- The subarray is <code>[1,6]</code>. There is only one pair: <code>(1,6)</code> and it contains numbers with different parity. So the answer to this query is <code>true</code>.

**Constraints:**

- <code>1 <= nums.length <= 10⁵</code>
- <code>1 <= nums[i] <= 10⁵</code>
- <code>1 <= queries.length <= 10⁵</code>
- <code>queries[i].length == 2</code>
- <code>0 <= queries[i][0] <= queries[i][1] <= nums.length - 1</code>

## Solution 1
#### C++

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> isValid(1, 0);
        int cnt = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (((nums[i - 1] ^ nums[i]) & 1) == 0) {
                cnt++;
            }
            isValid.push_back(cnt);
        }

        vector<bool> res;
        for (vector<int>& query: queries) {
            res.push_back(isValid[query[0]] == isValid[query[1]]);
        }
        return res;
    }
};

>### Complexity
> n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |

## Note
x