Rotating array (Larray hackerrank)

Question

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) ?

I 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) ? — Marco Roberts
– Marco Roberts, Commented Mar 26, 2016 at 17:24
Please add (edit in) your exact question to your post. Not everybody here reads through all comments. — PM 77-1
– PM 77-1, Commented Mar 26, 2016 at 17:26

Sorin · Accepted Answer · 2016-03-26 18:10:05Z

2

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.

answered Mar 26, 2016 at 18:10

Sorin

12k25 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Rotating array (Larray hackerrank)

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related