Marco Roberts
Marco Roberts

Reputation: 205

Rotating array (Larray hackerrank)

I am not able to get the logic behind the solution to the problem . I will be very thankful if someone can explain me the working of it.

Solution:

#include <bits/stdc++.h>
using namespace std;
const int N=1509;
int n;
int a[N];

void input(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
}

void sol(){
    int K=1;
    for (int i=1;i<=n;i++)
    for (int j=i+1;j<=n;j++)
        K^=(a[i]>a[j]);
    if (K) printf("YES\n");
    else printf("NO\n");
}

int main() {
    int test;
    scanf("%d",&test);
    while (test--){
        input();
        sol();
        }
    return 0;
}

I am not able to get how after xoring each permutation, value of 'k' in the end is determining the answer(ie whether it can be arranged in sorting order) ?

Upvotes: 1

Views: 190

Answers (1)

Sorin
Sorin

Reputation: 11968

When you rotate a block you change the number of inversions by +/- 2 or 0 (work it out on paper, if you don't trust me). So if the number of inversions in the array is odd you will not be able make it sorted with the given operation. You'll end up with the array almost sorted with all but 2 elements in place (1 inversion) and you can't fix that with the given operation.

What the code does is check if the number of inversions is odd by xoring with itself every time it sees an inversion. You can get the same result if you count the inversions up and check inversions % 2 == 0.

Upvotes: 2

Related Questions