Header Ads Widget

Equal Parity Sum | hackerearth solution

 Problem

  You are given an array [1] containing  integers. You can apply the following operation atmost once :

  • Choose a subarray [] with1 and multiply 1 to all elements of the subarray.

Find if it possible to make the sum of integers on the odd indices of  equal to the sum of integers on the even indices.

 Input format

  • The first line contains  denoting the number of test cases. The description of  test cases is as follows:
  • For each test case:
    • The first line contains a single integer  denoting the size of array .
    • The second line contains  integers 1,2,, - denoting the elements of .

Output format

For each test case, print YES if it is possible to achieve to requied goal, otherwise print NO in a separate line.

Constraints

110525105109109Sum of  over all test cases does not exceed5105.

 

Sample Input
2
5
1 5 -2 3 -1
4
-10 7 9 -3
Sample Output
YES
NO

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

In the first test case, apply the operation on the subarray [34] making =[1,5,2,3,1], Now the sum of elements on the odd indices is 1+21=2, and the sum of elements on the even indices is 53=2.

In the second test case, it is impossible to achieve the goal.

Code(C++):-

#include <bits/stdc++.h>
using namespace std;
bool fun()
{
int n;
long long diff = 0, cur_diff = 0;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++)
{
cin >> v[i];
if(i & 1)
            diff += v[i];
else
            diff -= v[i];
}
if(diff & 1)
        return false;
    diff>>=1;
unordered_set<long long> s;
s.insert(0);
for(int i = 0; i < n; i++)
{
if(i & 1)
            cur_diff += v[i];
else
            cur_diff -= v[i];
if(s.find(cur_diff - diff) != s.end())
            return true;
s.insert(cur_diff);
}
return false;
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t = 1;
cin >> t;
while(t--)
cout << (fun() ? "YES\n" : "NO\n");
return 0;
}

Code(JAVA):-

import java.io.*;
import java.util.*;
class TestClass {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static StringTokenizer st;
static int mod = (int) 11;
public static void main(String[] args) throws IOException {
int T = readInt();
while (T-->0) {
int n = readInt();
int[] A = new int[n+1];
long oddSum = 0, evenSum = 0;
for (int i = 1; i <= n; i++) {
A[i] = readInt();
if (i%2==1) {
oddSum += A[i];
}
else evenSum += A[i];
}
long dif = (evenSum - oddSum); // sum of even - sum of odd
if (Math.abs(dif) % 2 == 1) {
System.out.println("NO");
continue;
}
dif /= 2;
System.out.println(solve(A, dif, n) ? "YES" : "NO");
}
}
public static boolean solve(int[] a, long exp, int n) {
Set<Long> set = new HashSet<>();
long sum = 0;
for (int i = 1; i <= n; i++) {
sum += (i%2==1 ? -a[i] : a[i]);
if (sum == exp) {
return true;
}
if (set.contains(sum - exp)) {
return true;
}
set.add(sum);
}
return false;
}
static String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine().trim());
return st.nextToken();
}
static long readLong() throws IOException {
return Long.parseLong(next());
}
static int readInt() throws IOException {
return Integer.parseInt(next());
}
static double readDouble() throws IOException {
return Double.parseDouble(next());
}
static char readCharacter() throws IOException {
return next().charAt(0);
}
static String readLine() throws IOException {
return br.readLine().trim();
}
static int readLongLineInt() throws IOException{
int x = 0, c;
while((c = br.read()) != ' ' && c != '\n')
x = x * 10 + (c - '0');
return x;
}
static long pow (long x, long exp){
if (exp==0) return 1;
long t = pow(x, exp/2);
t = t*t % mod;
if (exp%2 == 0) return t;
return t*x % mod;
}
static long lcm(long a, long b) {
return (a / gcd(a, b)) * b;
}
static long gcd(long a, long b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}

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