Header Ads Widget

Adjacent Parity | hackerearth solution

Problem

You are given an array A containing N integers. Find if it is possible to rearrange the elements of the array such that the parity of the sum of each pair of adjacent elements is equal (formally, (++1)=(++1) for each 1<1 ).

Here, parity refers to the remainder obtained when a number is divided by 2 (i.e. ()=mod2).

Input format

  • The first line contains denoting the number of test cases. The description of T test cases is as follows:
  • For each test case:
    • The first line contains denoting the size of array A.
    • The second line contains N space-separated integers A[1], A[2], ....., A[N] - denoting the elements of A.

Output format
For each test case, print "YES"(without quotes) if it is possible to reorder the array elements to satisfy the given condition and "NO"(without quotes) otherwise.

Constraints

110011001100

Sample Input
3
3 
1 3 2
4
1 3 2 5
5
5 2 2 7 1


Sample Output
YES
NO
YES
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The first test case

  • The given array already satisfies the required condition. Here (++1)=0 for each 12.

The second test case

  • There is no way to reorder the elements of the given array to satisfy the required condition.

The third test case

  • One possible reordering is [5, 2, 7, 2, 1].  Here (++1)=1 for each 14.


 Code(C++):-

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T,N;
    cin>>T;
    while(T--){
        cin>>N;
        int A[N];
        int even_count = 0,odd_count = 0;
        for(int i=0;i<N;i++){
            cin>>A[i];
            if(A[i]%2)
                odd_count++;
            else
                even_count++;
        }
        if(even_count == N || odd_count == N){
            cout<<"YES\n";
            continue;
        }
        if(abs(even_count - odd_count) <= 1){
            cout<<"YES\n";
            continue;
        }
        cout<<"NO\n";
    }
}

Code(JAVA):-

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
//BufferedReader
        String str = "";
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            str = br.readLine();
// Reading input from STDIN
        int testcases = Integer.parseInt(str);
        // TODO Auto-generated method stub
for(int i = 0;i < testcases; i++) {
    str = br.readLine();
    int len = Integer.parseInt(str);
    //actual logic
        String val = br.readLine();
        String[] tokens = val.split(" ");
        int[] ary = new int[tokens.length];
        int j = 0;
        for (String token : tokens){
         ary[j++] = Integer.parseInt(token);
        }
        j = 0;
        int odds = 0;
        int evens = 0;
        while (j< tokens.length) {
            if(ary[j] % 2 == 0) {
                evens++;
            }else {
                odds++;
            }
            j++;
        }
        if((evens ==0)||(odds ==0)||(odds == evens)) {
            System.out.println("YES");
        }else if((evens > odds)&&(evens - odds ==1)) {
            System.out.println("YES");
        }else if((odds > evens)&&(odds - evens ==1)) {
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }
    
}
    }
}


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:-