3 months ago

Suryansh Rishit • 0

Mysuru

Speacial Array

Approach

The problem asks us to determine if a sequence is "special" - meaning no two adjacent numbers have the same parity (both odd or both even).

Your approach is correct and efficient: Check adjacent pairs for parity conflicts.

Steps

1. Input Processing
   • Read the number of elements n
   • Read the array of n integers
2. Parity Check Algorithm
   • Iterate through the array from index 0 to n-2
   • For each pair of adjacent elements arr[i] and arr[i+1]:
     • Calculate a = arr[i] % 2 (0 if even, 1 if odd)
     • Calculate b = arr[i+1] % 2 (0 if even, 1 if odd)
     • If a == b, the elements have the same parity → sequence is NOT special
     • Return "NO" immediately
3. Success Case
   • If we complete the loop without finding any same-parity adjacent pairs
   • Return "YES" - the sequence is special

Code:

#include<bits/stdc++.h>

using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0 ; i < n;i++) cin >> arr[i];

    for(int i = 0 ; i < n-1;i++){
        int a = arr[i]%2;
        int b = arr[i+1]%2;
        if (a == b) {
            cout << "NO\n";
            return; 
        }
    }
    cout << "YES\n";


}


int main(){


    int t;
    cin >>t;

    while(t--){
        solve();
    }

}

Time Complexity

• O(n) - Single pass through the array

Space Complexity

• O(n) - For storing the input array