Header Ads Widget

Equal Parity | hackerearth solution

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

110411051109

The sum of   over all test cases does not exceed 2105.

 

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