Header Ads Widget

Equal Parity Sum | hackerearth solution

Rajnish Tripathi 05:30

 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

1≤�≤1052≤�≤5⋅105−109≤��≤109Sum of � over all test cases does not exceed5⋅105.

 

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 �[3…4] making �=[1,5,2,−3,−1], Now the sum of elements on the odd indices is 1+2−1=2, and the sum of elements on the even indices is 5−3=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:-



Tags:

Post a Comment

0 Comments