Special Array I

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

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 <= 100
• 1 <= nums[i] <= 100

Similar Problem

[Special Array II](special-array-ii)

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/TSbpUdMmx38" frameborder="0" allowfullscreen></iframe></div>

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

Java

class Solution {
    public boolean isArraySpecial(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if ((nums[i] % 2) == (nums[i - 1] % 2)) {
                return false;
            }
        }
        return true;
    }
}

Python

class Solution:
    def isArraySpecial(self, nums: List[int]) -> bool:
        for i in range(1, len(nums)):
            if (nums[i] % 2) == (nums[i - 1] % 2):
                return False
        return True

Complexity

• ⏰ Time complexity: O(n), where n 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 of num (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

Java

class Solution {
    public boolean isArraySpecial(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (((nums[i] & 1) ^ (nums[i - 1] & 1)) == 0) {
                return false;
            }
        }
        return true;
    }
}

Python

class Solution:
    def isArraySpecial(self, nums: List[int]) -> bool:
        for i in range(1, len(nums)):
            if (nums[i] & 1) == (nums[i - 1] & 1):
                return False
        return True