Adjacency Love solution codechef – An array is called lovely if the sum of product of each adjacent pair of elements is odd.
More formally, the array SS of size MM is lovely if the value ∑M−1i=1∑i=1M−1 (Si.Si+1)(Si.Si+1) is odd.
Adjacency Love solution codechef
You are given an array AA consisting of NN positive integers. Find a permutation of array AA which is lovely.
If multiple such permutations are possible, output any. If there is no lovely permutation, output -1.
Input Format
- The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
- The first line of each test case contains an integer NN.
- The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
Output Format
For each test case, if a lovely permutation of AA is possible, print a single line containing NN integers denoting the elements of any lovely permutation of AA. Otherwise, print -1.
Constraints
- 1≤T≤10001≤T≤1000
- 2≤N≤5002≤N≤500
- 1≤Ai≤1061≤Ai≤106
Adjacency Love solution codechef
- Subtask 1 (100 points): Original constraints.
Sample Input 1
2
5
1 2 3 4 10
3
7 11 145
Sample Output 1
3 1 10 2 4
-1
Adjacency Love solution codechef
Test Case 11: The sum of products of adjacent pair of elements of the given array is 1⋅2+2⋅3+3⋅4+4⋅10=2+6+12+40=601⋅2+2⋅3+3⋅4+4⋅10=2+6+12+40=60. Since this value is even, this is not a lovely permutation of the array.
A lovely permutation of the given array is [3,1,10,2,4][3,1,10,2,4]. The sum of products for this array would be 3⋅1+1⋅10+10⋅2+2⋅4=413⋅1+1⋅10+10⋅2+2⋅4=41, which is odd.
Test Case 22: No permutation of the given array exists where the sum of products of adjacent pair of elements is odd. Thus, answer is −1−1.