Equal Parity | hackerearth solution

Rajnish Tripathi 21:04

 Problem

You are given an array A containing 2⋅� 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 �,�(1≤�,�≤�,�≠�) such that �� is an even integer, then set ��=��2,��=��⋅2

 Input format

  • The first line contains T 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⋅� denotes size of array A.
    • The second line contains 2⋅� space-separated integers �1,�2,…,�2⋅� - 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≤�≤1041≤�≤1051≤��≤109

The sum of  � over all test cases does not exceed 2⋅105.

 

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 �=[4,10,1,3] 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;
FastReader in = new FastReader(inputStream);
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;
public void fillInputParams(FastReader in) {
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 class FastReader {
static final int BUFSIZE = 1 << 20;
static byte[] buf;
static int index;
static int total;
static InputStream in;
public FastReader(InputStream is) {
try {
in = is;
buf = new byte[BUFSIZE];
} catch (Exception e) {
}
}
private int scan() {
try {
if (index >= total) {
index = 0;
total = in.read(buf);
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:-

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: