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] <= 100In this approach, we will iterate over the array and check each pair of adjacent elements. We'll verify if they have different parity by comparing them using modulus operation. If all adjacent pairs have different parity, the array is special.
This C function iterates through the array checking each adjacent pair's parity. It returns false if any pair has the same parity, otherwise returns true.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1).
For this approach, we use XOR to check the parity of adjacent elements. Two numbers have different parity iff (x % 2) ^ (y % 2) is true. We loop through the array and if the XOR of adjacent parities is zero, return false.
This C function uses the XOR operation on the parities of adjacent elements to determine if they differ.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Iterative Check | Time Complexity: O(n) where n is the length of the array. |
| Using XOR for Parity Check | Time Complexity: O(n). |
This is the Most Asked FAANG Interview Question! - Two Sum - Leetcode 1 • Greg Hogg • 649,221 views views
Watch 9 more video solutions →Practice Special Array I with our built-in code editor and test cases.
Practice on FleetCode