Make All Bulbs the Same

Author : adithya19

Required Knowledge : Greedy, Math

Time Complexity : $O(N)$

Editorialist : adithya19

Approach:

There are two possibilities: either make all bulbs ON or make all bulbs OFF

To make all bulbs ON, make a copy $S$ of the original string and scan from $i = 0$ to $N–2$. Whenever you see $S[i] == '0'$, flip both $S[i]$ and $S[i+1]$; this guarantees that by the time you reach the end, positions $0$ through $N–2$ are all '1'. If the final bulb $S[N–1]$ is also '1', you have turned every bulb $ON$.

Similarly, To make all bulbs OFF, copy into $S1$ and for each $i = 0$ to $N–2$, if $S1[i] == '1'$, flip both $S1[i]$ and $S1[i+1]$. Now The positions from $0$ through $N–2$ are all '0'. if $S1[N–1]$ ends up '0', you’ve made the whole set of bulbs $OFF$. If either pass succeeds, print "YES", otherwise "NO".

Code:

/* Author: T. Adithya Sai Ram :: adithya19 :: */
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <tuple>
using namespace std;
#define ll              long long
#define vll             vector<ll>
#define pb              push_back
#define NN              1000000
#define mod             1000000007
#define tot(a)          a.begin(),a.end()
#define mini(a)         *min_element(tot(a))
#define maxi(a)         *max_element(tot(a))
#define ppb             pop_back
#define read(a)         for(auto &x : a) cin >> x;
#define print(a)        for(ll i : a) cout << i <<" ";
#define yes             cout << "YES" << endl;
#define no              cout << "NO" << endl;
#define u_m             unordered_map
#define pll             pair<ll, ll>
#define vpll            vector<pll>
#define F               first
#define S               second
#define endl            "\n"

// ------------------------------------------------------------------------------------
void solve()
{
    ll n;
    cin>>n;
    string s;
    cin>>s;

    string s1=s;
    for(ll i=0;i<n-1;i++){
        if(s[i] == '0'){
            s[i]='1';
            if(s[i+1] == '0') s[i+1]='1';
            else s[i+1]='0';
        }
    }

    for(ll i=0;i<n-1;i++){
        if(s1[i] == '1'){
            s1[i]='0';
            if(s1[i+1] == '0') s1[i+1]='1';
            else s1[i+1]='0';
        }
    }

    ll c1=0,c2=0;
    for(ll i=0;i<n;i++){
        if(s[i] == '1'){
            c1++;
        }
        if(s1[i] == '0'){
            c2++;
        }
    }
    if(c1 == n || c2 == n){
        cout<<"yes"<<endl;
    }
    else{
        cout<<"no"<<endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll t=1;
    cin>>t;
    while(t--)
    {
       solve();
    }
    return 0;
}