There is no need to take segments, we can go with whole array.

If all elements are equal to $$$0$$$, we don't need to do anything, so the answer is $$$0$$$.

If there is any bit $$$\leq k$$$ which is set to $$$0$$$ for all $$$a_i$$$, then answer will be $$$1$$$.

If $$$k$$$ is $$$1$$$, then answer is $$$−1$$$, in all other cases answer is $$$2$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    int t;
    cin>>t;
    while(t--){
        int n,x;
        cin>>n>>x;
        vector<int> a(n);
        for(int i=0;i<n;i++) cin>>a[i];
        int cnt=count(a.begin(),a.end(),0);
        if(cnt==n) cout<<0<<endl;
        else if(x==1){
            for(int i=0;i<n;i++) a[i]=a[i]&1;
            int cnt=count(a.begin(),a.end(),0);
            if(cnt==n) cout<<1<<endl;
            else cout<<-1<<endl;
        }
        else{
            bool ok=false;
            for(int i=0;i<31;i++){
                int cnt=0;
                for(int j=0;j<n;j++){
                    if((a[j]&(1<<i))==0) cnt++;
                }
                if(cnt==n && x>=(1<<i)){
                    ok=true;
                    break;
                }
            }
            if(ok) cout<<1<<endl;
            else cout<<2<<endl;
        }
    }
}

If $$$n=1$$$, then the answer is YES if and only if $$$x=y$$$.

Otherwise, we consider each binary bit of $$$x$$$ and $$$y$$$.

If there is any bit which is set to $$$0$$$ in $$$x$$$ and to $$$1$$$ in $$$y$$$, then the answer is NO.

Let $$$c$$$ be the number of bits set to $$$1$$$ in $$$x$$$ and to $$$0$$$ in $$$y$$$. There can be at most $$$2^c$$$ different elements in $$$a$$$. So just check if $$$n \leq 2^c$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,x,y;

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d%d",&n,&x,&y);
		if(n==1) printf("%s\n",(x==y)?"YES":"NO");
		else
		{
			int flg=1,sz=1;
			for(int i=0;i<30;i++)
			{
				int bx=((x&(1<<i))!=0),by=((y&(1<<i))!=0);
				if((!bx)&&by)      flg=0;
				else if(bx&&(!by)) sz<<=1;
			}
			if(n>sz) flg=0;
			printf("%s\n",flg?"YES":"NO");
		}
	}
	
	//fclose(stdin);
	return 0;
}

Let $$$p_0$$$ be the first occurrence of $$$0$$$. It's not hard to find that $$$a_{p_0}$$$ cannot be increased, since in order to make $$$a_{p_0} > 0$$$, $$$a_i = 0$$$ should exist for $$$i < p_0$$$. So, we cannot make any $$$a_i = 0$$$, for $$$i > p_0$$$, because MEX($$$a_0, a1, \ldots, a{i-1}$$$) $$$\ge 1$$$. However, we can apply operations for $$$i = p_0, p_0 - 1, \ldots, 2, 1$$$, obtaining $$$a_i = 0$$$, for each $$$i \in [1, p_0]$$$.

After that, let's find the first occurrence of $$$1$$$ — $$$p_1$$$. (If there are no $$$1$$$s in the sequence, let $$$p_1 = n$$$). Similarly, we can apply operations for each $$$i = p_1, p_1 - 1, \ldots p_0 + 1$$$, where $$$a_i \le 1$$$, obtaining $$$a_i = min(a_i, 1)$$$, for each $$$i \in [p_0, p_1]$$$.

Increasing the value, we repeat the process, while $$$[1, p_0] \cup [p_0, p_1] \cup \ldots \cup [p_{k-1}, p_k] \ne [1, n]$$$.

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(0);
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] == cur) {
                ++cur;
            }
            a[i] = min(a[i], cur);
        }
        for (auto el : a) {
            cout << el << " ";
        }
        cout << endl;
    }
    return 0;
}

Let's find an $$$i$$$ such that $$$a_i \ne b_i$$$. If $$$a_1 \oplus \ldots a_{i - 1} = 1$$$, then we can flip $$$a_i$$$ straightaway. Otherwise, let $$$cnt$$$ be the number of indices $$$j$$$ such that $$$a_j = 1, j < i$$$. If $$$cnt = 0$$$, then we cannot flip $$$a_j$$$ for all $$$1 \le j \le i$$$, so the answer is $$$-1$$$. So now $$$cnt \ge 2$$$. Let $$$j_2$$$ be the second position for which $$$a_{j_2} = 1$$$. Let's flip $$$a_{j_2}$$$, then flip $$$a_i$$$ and once again flip $$$a_{j_2}$$$. Since for every $$$i$$$ such that $$$a_i \ne b_i$$$, we apply at most $$$3$$$ operations, there are at most $$$3 \cdot n$$$ operations in total.

Let $$$i_1, i_2, \ldots, i_k$$$ be the indices that we need to flip in $$$a$$$. Let's iterate over them in increasing order and flip indices that we can ($$$cnt$$$ should be odd). After that, we know that for all remaining indices, corresponding $$$cnt$$$ is even. We can make corresponding $$$cnt$$$s odd by flipping the second occurrence of $$$1$$$ in $$$a$$$ — $$$j_2$$$, then we can flip all remaining $$$i_1, i_2, \ldots, i_k$$$ in reverse order, and finally flip $$$a_{j_2}$$$ back.

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(0);
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        string a, b;
        cin >> a;
        cin >> b;
        vector<int> ans;
        vector<int> ones;
        int fl = true;
        for (int i = 0; i < n; ++i) {
            if (a[i] != b[i]) {
                if (ones.empty()) {
                    fl = false;
                    break;
                }
                int k = (int)ones.size();
                if (k % 2 == 1) {
                    ans.push_back(i);
                } else {
                    ans.push_back(ones[1]);
                    ans.push_back(i);
                    ans.push_back(ones[1]);
                }
            }
            if (b[i] == '1') {
                ones.push_back(i);
            }
        }
        if (!fl) {
            cout << -1 << endl;
            continue;
        }
        cout << ans.size() << endl;
        for (auto el : ans) {
            cout << el + 1 << " ";
        }
        cout << endl;
    }
    return 0;
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n;
int  a[N],b[N];
char s[N],t[N];

int check()
{
	int ca=0,cb=0;
	for(int i=1;i<=n;i++) ca+=a[i],cb+=b[i];
	if(!ca) return cb!=0;  
	for(int i=1;i<=n;i++) 
	{
	    if(a[i]) return (!b[i]);
	    else if(b[i]) return 1;
	}
}

int main()
{
	//freopen("1.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
	    scanf("%d%s%s",&n,s,t);
	    for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
	    for(int i=1;i<=n;i++) b[i]=t[i-1]-'0';
	    if(check())
	    {
    		printf("-1\n");
    		continue;
    	}
	    int p=INF,x=0;
	    vector<int> ans;
	    for(int i=1;i<=n;i++)
	    {
    		if(a[i])
    		{
		    	p=i+1;
		    	break;
		    }
    	}
	    if(p<=n)
	    {
    		for(int i=1;i<=n;i++)
  	 	    {
    			x^=a[i];
    			if((a[i]!=b[i])&&x==b[i]&&i>p)
    			{
		    		ans.push_back(i);
		    		x^=1;a[i]^=1;
		    	}
    		}
    		a[p]^=1;ans.push_back(p);
    		for(int i=n;i>=p;i--) if(a[i]^b[i]) ans.push_back(i);
    	}
    	printf("%d\n",ans.size());
    	if(!ans.size()) printf("\n");
    	for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
	}
	
	//fclose(stdin);
	return 0;
}

For $$$i$$$ in range $$$1\le l \le r \le n$$$,

$$$a_i \bmod m = b_i$$$

$$$\Rightarrow (a_i-b_i) \bmod m =0$$$

$$$\Rightarrow m \text{ divides } (a_i-b_i)$$$

Therefore, the biggest possible value of $$$m$$$ is gcd of all $$$(a_i-b_i)$$$ $$$(l \le i \le r)$$$ (except when $$$gcd=0$$$, then $$$m$$$ can be arbitrarily large).

But we need the smallest value of $$$m$$$, so we will find the smallest factor of $$$m$$$ strictly greater than all $$$b_i$$$ $$$(l \le i \le r)$$$.

To efficiently answer the queries, we can use some data structures like segment tree or sparse table to find the range gcd of $$$(a_i-b_i)$$$ in range and also to find the maximum value of $$$b_i$$$ in the range.

We will also need to do some precomputation for finding the factors of the gcd we obtained. Then, we can do binary search over the factors, to find the smallest factor strictly greater than the maximum value of $$$b_i$$$ in the range.

We will print -1 when we are unable to find any such $$$m$$$, like when $$$(a_i-b_i)$$$ is negative for some $$$i$$$ in or no factor of $$$gcd$$$ is strictly greater than the maximum value of $$$b_i$$$ in the range.

#include<bits/stdc++.h>
using namespace std;
 
//#define int long long
#define endl "\n"
 
const int N=1000001;
 
vector<vector<int>>divisors(N);
 
void init_sparse_max(vector<int>&a,vector<vector<int>>&dp){
    int n=a.size();
    for(int i=0;i<n;i++){
        dp[i][0]=a[i];
    }
    for(int j=1;j<30;j++){
        for(int i=0;i+(1LL<<j)-1<n;i++){
            dp[i][j]=max(dp[i][j-1],dp[i+(1LL<<(j-1))][j-1]);
        }
    }
}
 
void init_sparse_gcd(vector<int>&a,vector<vector<int>>&dp){
    int n=a.size();
    for(int i=0;i<n;i++){
        dp[i][0]=a[i];
    }
    for(int j=1;j<30;j++){
        for(int i=0;i+(1LL<<j)-1<n;i++){
            dp[i][j]=__gcd(dp[i][j-1],dp[i+(1LL<<(j-1))][j-1]);
        }
    }
}
 
int query_max(int l,int r,vector<vector<int>>&dp){
    int j=log2(r-l+1);
    int ans=max(dp[l][j],dp[r-(1LL<<j)+1][j]);
 
    return ans;
}
 
int query_gcd(int l,int r,vector<vector<int>>&dp){
    int j=log2(r-l+1);
    int ans=__gcd(dp[l][j],dp[r-(1LL<<j)+1][j]);
 
    return ans;
}
 
void solve(){
    int n,q;
    cin>>n>>q;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<int>b(n);
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    vector<vector<int>>sparse_max(n,vector<int>(30));
    init_sparse_max(b,sparse_max);
    vector<int>c(n);
    set<int>st;
    for(int i=0;i<n;i++){
        c[i]=a[i]-b[i];
        if(c[i]<0){
            st.insert(i);
        }
    }
    vector<vector<int>>sparse_gcd(n,vector<int>(30));
    init_sparse_gcd(c,sparse_gcd);
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;r--;
        auto it=st.lower_bound(l);
        if(it!=st.end() && *it<=r){
            cout<<-1<<endl;
            continue;
        }
        int m=query_gcd(l,r,sparse_gcd);
        int maxi=query_max(l,r,sparse_max);
        int index=upper_bound(divisors[m].begin(),divisors[m].end(),maxi)-divisors[m].begin();
        if(index!=(int)divisors[m].size()){
            cout<<divisors[m][index]<<endl;
        }else{
            cout<<-1<<endl;
        }
    }
}
 
signed main(){
 
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
 
    for(int i=1;i<=1000000;i++){
        for(int j=i;j<=1000000;j+=i){
            divisors[j].push_back(i);
        }
    }
 
    int t;
    cin>>t;
    while(t--){
        solve();
    }
 
    return 0;
}

Soon...

Soon...