[Solution] Odd Swap Sort solution codeforces

Odd Swap Sort solution codeforces – You are given an array 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an. You can perform operations on the array. In each operation you can choose an integer 𝑖i (1𝑖<𝑛1≤i<n), and swap elements 𝑎𝑖ai and 𝑎𝑖+1ai+1 of the array, if 𝑎𝑖+𝑎𝑖+1ai+ai+1 is odd.

Determine whether it can be sorted in non-decreasing order using this operation any number of times.

Odd Swap Sort solution codeforces

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1𝑡1051≤t≤105) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer 𝑛n (1𝑛1051≤n≤105) — the length of the array.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109) — the elements of the array.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105.


For each test case, print “Yes” or “No” depending on whether you can or can not sort the given array.

You may print each letter in any case (for example, “YES”“Yes”“yes”“yEs” will all be recognized as positive answer).

Odd Swap Sort solution codeforces

1 6 31 14
4 2
2 9 6 7 10
6 6 6


Odd Swap Sort solution codeforces

In the first test case, we can simply swap 3131 and 1414 (31+14=4531+14=45 which is odd) and obtain the non-decreasing array [1,6,14,31][1,6,14,31].

In the second test case, the only way we could sort the array is by swapping 44 and 22, but this is impossible, since their sum 4+2=64+2=6 is even.

In the third test case, there is no way to make the array non-decreasing.

In the fourth test case, the array is already non-decreasing.


Leave a Comment