Header Ads Widget

Adjacency Hatred | codechef solution

Rajnish Tripathi 22:48

 An array is called lovely if the sum of absolute differences of each adjacent pair of elements is odd; formally, the array 

� of size � is lovely if ∑�=1�−1 ∣��−��+1∣ is odd.

You are given an array � of � integers. You need to reorder the array in any manner such that the array becomes lovely. If there is no reordering operation that makes the array lovely, output -1.

Input Format

  • The first line contains an integer � denoting the number of test cases. The � test cases then follow.
  • The first line of each test case contains an integer �.
  • The second line of each test case contains � space-separated integers �1,�2,…,��.

Output Format

For each test case, print a single line containing � integers denoting the modified array which is lovely, or -1 if it is not possible.

Constraints

  • 1≤�≤1000
  • 2≤�≤500
  • 1≤��≤106

Sample 1:

Input
Output
2
6
3 7 10 1 2 12
2
1 3

1 2 3 10 7 12
-1

Explanation:

  • For the first test case, the sum is ∣1−2∣+∣2−3∣+∣3−10∣+∣10−7∣+∣7−12∣=1+1+7+3+5=17 which is odd.

  • For the second test case, ∣1−3∣=2 which is even. There is no array that can satisfy the above condition.

Code(C++):-
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX INT_MAX
#define MIN INT_MIN
#define mod 1000000007
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vector<int>>
#define endl "\n";
#define pb push_back

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
ll arr[n];
vector<ll>odd,even;
for(int i=0;i<n;i++){
cin>>arr[i];
if(arr[i]%2==0) even.pb(arr[i]);
else odd.pb(arr[i]);
}
int oo=odd.size();
int ee=even.size();
if(oo==0 ||ee==0){
cout<<-1<<endl;
continue;
}
int i=0,j=0;
sort(odd.begin(),odd.end());
sort(even.begin(),even.end());
for(int i:even){
cout<<i<<" ";
}
for(int i:odd)
cout<<i<<" ";

cout<<endl;
}
return 0;
}


Code(JAVA):-
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
     Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        while(t-->0){
         int n = s.nextInt();
         int[] a = new int[n];
         for(int i = 0;i<n;i++){
         a[i] = s.nextInt();
         }
         int even = 0;
         int odd = 0;
         for(int i: a){
         if((i&1)==0){
         even++;
         }
         else{
         odd++;
         }
         }
         if(odd==n||even==n){
         System.out.println(-1);
         }
         else{
         int[] ans = new int[n];
         int st = 0;
         int end = n-1;
         for(int i: a){
         if((i&1)==0){
         ans[end--]=i;
         }
         else{
         ans[st++]=i;
         }
         }
         for(int i: ans){
         System.out.print(i+" ");
         }
         System.out.println();
         }
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-



Tags:

Post a Comment

0 Comments