# Bitwise swaps BITSWAPS Solution Codechef

## Bitwise swaps BITSWAPS Solution

Given an array A consisting of N integers A1,A2,…,AN, determine if you can sort this array by applying the following operation several times (possibly, zero):

• Pick a pair of indices (i,j) with i≠j and Ai&Aj≠0, and swap the values of Ai and Aj. Here, & denotes the bitwise AND operation.

For example, if A=[6,4,2], the two possible operations are (1,2) and (1,3) (2,3) cannot be performed because A2&A3=4&2=0.

Input Format

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N.
• The second line contains N space-separated integers A1,A2,…,AN

Output Format

• For each test case, output the answer on a new line `YES` if the given array can be sorted by repeatedly applying the given operation, and `NO` otherwise.
• You may print each character of the answer string in either uppercase or lowercase (for example, the strings `"yEs"``"yes"``"Yes"` and `"YES"` will all be treated as identical).

Constraints

• 1≤T≤104
• 1≤N≤3⋅105
• 0≤Ai<231 for each 1≤i≤N
• The sum of N over all test cases does not exceed 3⋅105

Subtask #1 (100 points): Original constraints

Sample Input 1

``````4
3
6 4 2
6
9 34 4 24 1 6
6
9 34 24 4 1 6
2
1 0``````

Sample Output 1

``````Yes
Yes
No
No``````

Explanation

Test case 1: A can be sorted by applying the single operation (1,3).

Test case 2: A can be sorted by applying the following operations in order: (1,5),(2,6),(2,3),(4,5).

Test cases 3 and 4: It can be shown that no sequence of operations will sort A.

### SOLUTION

Program: Bitwise swaps BITSWAPS Solution in C++

``````#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
map<int,int> mp;
vector<int> arr(n),temp(n);
for(int i=0;i<n;i++){
cin>>arr[i];
mp[arr[i]]=i;
temp[i] = arr[i];
}

sort(temp.begin(),temp.end());
vector<int> visited(n,0),visBit(32,0);
int k = 1;
for(int i=0;i<32;i++){
unsigned int nN = 1<<i;
for(int j=i;j<32;j++){
unsigned int t = 1<<j;
if(visBit[j]||(nN&t)==0)
continue;
visBit[j] = 1;
for(int l=0;l<n;l++){
bool cnd = ((visited[l]==0)&&(arr[l]&nN));
if(cnd){
nN = nN|arr[l];
visited[l]=k;
}
}

}
k++;
}
k=1;
for(int i=0;i<n;i++)
auto itr = mp.find(temp[i]);
if(visited[i]!=visited[itr->second]){
k=0;
break;
}
}
if(k)
cout<<"Yes\n";
else
cout<<"No\n";
}
return 0;
}``````