Array Modification MARM code editorial (unofficial)

editorial
,
1

So the general idea is that if a and b are two numbers then

a xor b = a X b
then again for next step

  • a X b X b = a

2nd step a X b X a = b
and b X a = b X a

in 3rd step we will get back the original pair

a b .
So we can use this property of XOR to reduce the number of comparisons .

#include<bits/stdc++.h>
using namespace std;

int main(){
    long long t;
    cin>>t;
    while(t--){
        long long n,k;
        cin>>n>>k;
        long long col[n];
        for(int i=0;i<n;i++){
            cin>>col[i];
        }
        long long number=k/n;
        long long mod=number%3;
        if(k>n &&n%2!=0){
            col[n/2]=0;
        }
        while(mod>0){
            int l=0,m=n-1;
        for(int i=0;i<n;i++){
            col[i]=col[l]^col[m];
            l=(l+1)%n;
            m=((m-1)+(n))%n;
        }
        mod--;
       
        }
        long long rem=k%n;
        int l=0,m=n-1;
         for(int i=0;i<rem;i++){
            col[i]=col[l]^col[m];
            l=(l+1)%n;
            m=((m-1)+(n))%n;
            }

        for(int i=0;i<n;i++){
            cout<<col[i]<<" ";
        }
        cout<<endl;
    }
}
2 Likes