---
# System prepended metadata

title: LC 3152. Special Array II
tags: [medium, leedcode, c++]

---

# 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<sub>i</sub>, to<sub>i</sub>]</code> your task is to check that subarray <code>nums[from<sub>i</sub>..to<sub>i</sub>]</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<sub>i</sub>..to<sub>i</sub>]</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<sup>5</sup></code>
- <code>1 <= nums[i] <= 10<sup>5</sup></code>
- <code>1 <= queries.length <= 10<sup>5</sup></code>
- <code>queries[i].length == 2</code>
- <code>0 <= queries[i][0] <= queries[i][1] <= nums.length - 1</code>

## Solution 1
#### C++
```cpp=
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
