Problem
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
.
Examples
Example 1:
|
|
Example 2:
|
|
Example 3:
|
|
Constraints
1 <= nums.length <= 100
1 <= nums[i] <= 100
Similar Problem
Solution
Video explanation
Here is the video explaining below methods in detail. Please check it out:
Method 1 - Iteration
An array is considered special if every pair of its adjacent elements contains two numbers with different parity (one even and one odd, or vice versa).
- A number is odd if
number % 2 == 1
- A number is even if
number % 2 == 0
- To verify that an array is special, we need to check each pair of adjacent elements.
Here is the approach:
- Iterate through the array checking each pair of adjacent elements.
- Ensure they have different parity.
- If any pair has the same parity, return
false
. - If all pairs have different parities, return
true
.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
, wheren
is the length of the array because we check each pair of adjacent elements. - 🧺 Space complexity:
O(1)
since we only use a constant amount of extra space.
Method 2 - Using XOR
XOR has a useful property: if you XOR two bits, the result is 1 if the bits are different, and 0 if they are the same.
- For binary representation of numbers, the least significant bit (LSB) indicates parity:
0
for even,1
for odd. - Therefore,
num & 1
gives us the parity ofnum
(0 for even, 1 for odd).
Approach
- Iterate through the array starting from the second element.
- For each pair of adjacent elements, use the XOR operation to check their parities. If both have the same parity, their XOR result will be 0.
- If there’s any pair with the same parity, return
false
. - If all pairs have different parities, return
true
.
Code
|
|
|
|