# PROBLEM LINK:

* Author:* Ritesh Gupta

*Sachin Yadav*

**Tester:***Ritesh Gupta*

**Editorialist:**# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

BITS, PREFIX-SUFFIX, OBSERVATION

# PROBLEM:

You are given a circular sequence A_1, A_2, \ldots, A_N (3 \le N \le 2*10^5 \space and \space 0 \le A_i \le 10^9) where the elements are in the clockwise order and an integer K(0 \le K \le 10^9). You can change the value at any index by applying some operations. In one operation, you can select some index and replace the value at that index by **bitwise or** of the values of two adjacent elements of the current element i.e. if we apply the operation on i_{th} index then the value of A_i is equal to A_{i-1} or A_{i+1}.

Perform the above-mentioned operation over each index (**exactly once**) of the circular sequence in any order such that **bitwise or** of the elements of the resultant sequence is K.

# QUICK EXPLANATION:

- Let suppose, if the answer is always possible then we need to remove first that elements which have a set bit that is not set in K. After then we can apply the operation on the rest of the indexes in such a way that we choose the index whose adjacent index had already been affected by the operation.
- If there is no element that has a set bit that is not set in K then we start operation from the index whose contribution is not required in clockwise order and cover all the indexes without skipping any.

# EXPLANATION:

Let’s define an element **good** or **bad**. An i_{th} index element is said to be **good** if (A_i \space or \space K) == K else it is said to be **bad**. The answer is defined as the **bitwise or** of the elements of the resultant sequence.

**OBSERVATION:**

- The value of N should be greater than and equal to 3 as given in the question.
- If or of all the
**good**elements of the sequence is not equal to k then the answer is -1. - The
**first element**where the operation applied makes sure that its adjacent element contribution is present in answer. So, if there are two**bad**elements in the sequence that are adjacent to each other then the answer is -1. - It does not matter in which way we apply the operation but is sure that at least one element (the
**first element**where the operation applied) should not contribute in answer. So, If the array has only**good**elements and all of them have some set bit which is not in others then the answer is -1 otherwise the answer is equal to K**always**possible.

If the answer exists then we perform the operation on **bad** elements in any order and after that on **good** elements in some order such that all the elements give their contribution into the answer. To make sure that we apply the operation on good elements from the right adjacent element of any **bad** element in the clockwise direction.

If all the elements are **good** then we can use the prefix-suffix technique to solve the problem as we know at least one index should not contribute to the answer. Let P_i and S_i is defined as **bitwise-or** of a prefix which ends at i^{th} index and **bitwise-or** of a suffix which starts at i^{th} index respectively. So, answer can be equal to:

- P_{N-1}
- S_1
- P_{i-1} + S_{i+1} for i form 1 to N-1

Now, suppose the contribution of i_{th} index element is not required in the answer, and answer is equal to K then we can apply the operation over the sequence from the i_{th} element in clockwise order.

## Bonus Problem

- Try to find the lexicographically smallest solution among all possible ones.

# COMPLEXITY:

**TIME:** O(N)

**SPACE:** O(N)

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[200010];
int b[200010];
bool vis[200010];
int32_t main()
{
int t;
cin >> t;
while(t--)
{
int n,k;
cin >> n >> k;
bool flag = false;
for(int i=0;i<n;i++)
{
cin >> a[i];
vis[i] = false;
if((a[i] | k) != k)
vis[i] = flag = true;
}
if(!flag)
{
for(int i=0;i<n;i++)
b[i] = a[i];
b[n] = 0;
for(int i=n-1;i>=0;i--)
b[i] = (b[i] | b[i+1]);
int cnt = 0;
flag = false;
for(int i=0;i<n;i++)
{
if((cnt | b[i+1]) == k)
{
cnt = i;
flag = true;
break;
}
cnt = (cnt | a[i]);
}
if(flag)
{
for(int i=cnt;i<n;i++)
cout << i+1 << " ";
for(int i=0;i<cnt;i++)
cout << i+1 << " ";
cout << endl;
}
else
cout << -1 << endl;
continue;
}
vis[n] = vis[0];
flag = false;
for(int i=1;i<=n;i++)
{
if(vis[i] && (vis[i] == vis[i-1]))
{
flag = true;
break;
}
}
if(flag)
{
cout << -1 << endl;
continue;
}
if(vis[0])
a[0] = (a[n-1] | a[1]);
int cnt = a[0];
a[n] = a[0];
for(int i=1;i<n;i++)
{
if(vis[i])
a[i] = (a[i-1] | a[i+1]);
cnt = (cnt | a[i]);
}
if(cnt == k)
{
for(int i=0;i<n;i++)
{
if(vis[i])
cout << i+1 << " ";
}
int prev = 0;
for(int i=0;i<n;i++)
{
if(vis[i])
{
int j = i;
while(j != prev)
{
cout << j << " ";
j--;
}
prev = i+1;
}
}
int j = n;
while(j != prev)
{
cout << j << " ";
j--;
}
cout << endl;
}
else
cout << -1 << endl;
}
}
```

## Tester's Solution

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll const max_N=2e5+50;
ll T, N, K, arr[max_N];
bool bad[max_N];
void sol1();
void sol2();
void solve()
{
bool all_good=true;
memset(bad, 0, N+10);
ll or_good=0;
for(int i=1; i<=N; i++)
bad[i]=((arr[i] | K) != K);
for(int i=1; i<=N; i++)
{
int j=i+1;
if(j>N) j=1;
if(bad[i])
{
all_good=false;
if(bad[j])
{
cout<<-1;
return ;
}
}
else or_good|=arr[i];
}
if(or_good != K)
{
cout<<-1;
return ;
}
if(all_good)
sol1();
else
sol2();
}
void sol2()
{
int fst=N;
for(int i=1; i<=N; i++)
if(bad[i]){ cout<<i<<" "; fst=min(i, fst); }
for(int j=fst-1; j>=1; j--)
cout<<j<<" ";
for(int i=fst+1; i<=N; i++)
if(!bad[i]) cout<<i<<" ";
}
void sol1()
{
ll pre_or, suff_or[N+2];
pre_or=suff_or[N+1]=0;
for(int i=N; i>=1; i--)
suff_or[i]=suff_or[i+1] | arr[i];
for(int i=1; i<=N; i++)
{
if((pre_or | suff_or[i+1]) == K)
{
for(int j=i; j<=N; j++)
cout<<j<<" ";
for(int j=1; j<i; j++)
cout<<j<<" ";
return ;
}
pre_or|=arr[i];
}
cout<<-1;
}
int32_t main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>T;
while(T--)
{
cin>>N>>K;
for(int i=1; i<=N; i++)
cin>>arr[i];
solve();
cout<<"\n";
}
return 0;
}
```