# Equal Parity | hackerearth solution

Problem

You are given an array A containing $2\cdot �$ inetegers. You want to obtain exactly $�$ even integers in the array. Is it possible to achieve the goal using the following operation any number of times(possibly zero) ?

• Choose two distinct indices $�,\phantom{\rule{thickmathspace}{0ex}}�\phantom{\rule{thickmathspace}{0ex}}\left(1\le �,�\le �,�\ne �\right)$ such that ${�}_{�}$ is an even integer, then set ${�}_{�}=\frac{{�}_{�}}{2},\phantom{\rule{thickmathspace}{0ex}}{�}_{�}={�}_{�}\cdot 2$

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 an integer $�$ where $2\cdot �$ denotes size of array A.
• The second line contains $2\cdot �$ space-separated integers ${�}_{1},{�}_{2},\dots ,{�}_{2\cdot �}$ - denoting the elements of A.

Output format

For each test case, print "YES" (without quotes) if it is possible to achieve the goal and "NO" (without quotes) otherwise.

Constraints

$1\le �\le {10}^{4}\phantom{\rule{0ex}{0ex}}1\le �\le {10}^{5}\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}1\le {�}_{�}\le {10}^{9}$

The sum of  $�$ over all test cases does not exceed $2\cdot {10}^{5}$.

Sample Input
2
2
1 2 3 5
2
8 5 1 3


Sample Output
NO
YES

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case, it is impossible to have two even integers in the given array.

In the second test case, apply the operation on indices $�=1,�=2$ making $�=\left[4,10,1,3\right]$ which contains two even integers,

Code(C++):-

#include <bits/stdc++.h>
using namespace std;
int getCount(int num) {
int count = 0;
while (!(num & 1)) {
num >>= 1;
count++;
}
return count;
}
void solve(int n, vector<int> &nums) {
int evens = 0, powers = 0;
for (auto num : nums) {
if (!(num & 1)) {
evens++;
powers += getCount(num) - 1;
}
}
if (evens == n || powers >= n - evens) {
printf("YES\n");
} else {
printf("NO\n");
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
vector<int> nums(n << 1);
for (int i = 0; i < n << 1; i++) {
scanf("%d", &nums[i]);
}
solve(n, nums);
}
return 0;
}

Code(JAVA):-

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Map;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
PrintWriter out = new PrintWriter(outputStream);
EqualParity solver = new EqualParity();
int testCount = Integer.parseInt(in.next());
for (int i = 1; i <= testCount; i++)
solver.solve(i, in, out);
out.close();
}
static class EqualParity {
final boolean isDevEnv = System.getenv().get("USERDOMAIN") != null
&& System.getenv().get("USERDOMAIN").equals("LAPTOP-DSSUKMC1");
int N;
long[] A;
N = in.nextInt();
A = in.getLongArray(N * 2);
}
Object solveOptimised(FastReader in, StringBuilder sb) {
int count = 0;
for (long itr : A)
while (itr % 2 == 0) {
++count;
itr >>= 1;
}
return count >= N ? "YES" : "NO";
}
Object solveBrute(FastReader in, StringBuilder sb) {
if (!isDevEnv) return null;
return null;
}
public void solve(int testNumber, FastReader in, PrintWriter out) {
// out.print("Case #" + testNumber + ": ");
fillInputParams(in);
Object outOptimised = solveOptimised(in, new StringBuilder());
Object outBrute = solveBrute(in, new StringBuilder());
if (outBrute == null) {
out.println(outOptimised);
} else if (outBrute.toString().equals(outOptimised.toString())) {
System.err.println(testNumber + ". OK Checked");
} else {
// print input params
System.err.println("Actual = " + outOptimised);
System.err.println("Expected = " + outBrute);
System.err.println();
throw new ArithmeticException();
}
}
}
static final int BUFSIZE = 1 << 20;
static byte[] buf;
static int index;
static int total;
static InputStream in;
try {
in = is;
buf = new byte[BUFSIZE];
} catch (Exception e) {
}
}
private int scan() {
try {
if (index >= total) {
index = 0;
if (total <= 0)
return -1;
}
return buf[index++];
} catch (Exception | Error e) {
System.err.println(e.getMessage());
return 13 / 0;
}
}
public String next() {
int c;
for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder();
for (; c > 32; c = scan())
sb.append((char) c);
return sb.toString();
}
public int nextInt() {
int c, val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+')
c = scan();
for (; c >= '0' && c <= '9'; c = scan())
val = (val << 3) + (val << 1) + (c & 15);
return neg ? -val : val;
}
public long nextLong() {
int c;
long val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+')
c = scan();
for (; c >= '0' && c <= '9'; c = scan())
val = (val << 3) + (val << 1) + (c & 15);
return neg ? -val : val;
}
public long[] getLongArray(int size) {
long[] ar = new long[size];
for (int i = 0; i < size; ++i) ar[i] = nextLong();
return ar;
}
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-