An array is considered special if every pair of its adjacent elements contains two numbers with different parity.
You are given an array of integers nums. Return true if nums is a special array, otherwise, return false.
Example 1:
Input: nums = [1]
Output: true
Explanation:
There is only one element. So the answer is true.
Example 2:
Input: nums = [2,1,4]
Output: true
Explanation:
There is only two pairs: (2,1) and (1,4), and both of them contain numbers with different parity. So the answer is true.
Example 3:
Input: nums = [4,3,1,6]
Output: false
Explanation:
nums[1] and nums[2] are both odd. So the answer is false.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
Approach 01
-
C++
-
Python
class Solution {
public:
bool isArraySpecial(vector<int>& nums) {
int size = nums.size();
if (size == 1) {
return true;
}
for (int i = 1; i < size; ++i) {
// Check if two consecutive numbers have the same parity
if ((nums[i] & 1) == (nums[i - 1] & 1)) {
return false;
}
}
return true;
}
};
class Solution:
def isArraySpecial(self, nums: list[int]) -> bool:
size = len(nums)
if size == 1:
return True
for i in range(1, size):
# Check if two consecutive numbers have the same parity
if (nums[i] & 1) == (nums[i - 1] & 1):
return False
return True
Time Complexity:
- Single Pass Iteration:
We iterate through the array once, checking the parity of consecutive elements. This takes \( O(N) \) time.
- Overall Time Complexity:
\( O(N) \), where \( N \) is the number of elements in the array.
Space Complexity:
- Input Storage:
The input array is passed by reference, so it does not contribute to extra space usage.
- Constant Extra Space:
We only use a few integer variables, leading to an auxiliary space complexity of \( O(1) \).
- Overall Space Complexity:
\( O(1) \).