Bitwise swaps BITSWAPS Solution Codechef

by

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

Subtasks

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;
}

February Long 2022 – II (Rated for Div 3)

Leave a Comment

3 × three =