Special Array I

summary

• Check if an array is special, where every pair of adjacent elements contains two numbers with different parity.

approach

• Use a flag variable to track the parity of the first element
• Then, iterate through the array, updating the flag variable based on the parity of each element
• If a pair of adjacent elements has the same parity, return false
• Otherwise, return true if all pairs have different parity.

complexity

• O(n), where n is the number of elements in the array

explain

• The solution uses bitwise operations to check the parity of each element
• The expression `nums[i] & 1` checks if the least significant bit of `nums[i]` is 1 (i.e., the number is odd)
• The `flag ^ (nums[i] & 1)` expression updates the flag variable based on the parity of `nums[i]`
• If `flag` and `nums[i]` have different parity, `flag` is set to the opposite parity
• If they have the same parity, `flag` remains unchanged
• The solution returns false as soon as it encounters a pair of adjacent elements with the same parity, and returns true otherwise.

Solution Code:

class Solution {
public:
    bool isArraySpecial(vector& nums) {
        bool flag = nums[0] & 1;
        for(int i = 1; i < nums.size(); i++){
            if(flag ^ (nums[i] & 1)){
                flag ^= 1;
            } else{
                return false;
            }
        }
        return true;
    }
};