Odd or Even Sum

See the original problem on HackerRank.

You are given an array of integers A and you will be asked to answer some queries.

Each query is in the form:

1
i j

And you have to return the sum of absolute values from A[i] to A[j], that is:

1
A[i] + A[i+1] + ... + A[j]

Input Format

First Line of Input contains N and Q separated by space. Next Line contains N space separated integers. Next Q queries follows, each query contains two integers i and j separated by a space.

Constraints

1
2
3
4
1<= N <=100000
1<= Q <=100000
-9 <= A[i] <= 9
1<= i <= j <= N

Output Format

For each query output Even if the value is even, otherwise Odd.

Example

Input:

1
2
3
4
5
6
7
10 5
-8 -8 -8 4 -2 5 8 -5 1 2
2 9
8 10
1 3
3 4
6 8

Output:

1
2
3
4
5
Odd
Even
Even
Even
Even

Explanation:

Query 1 : abs(abs(abs(-5) + 1) + 2) = 8 => Even

Query 3 : abs(abs(abs(-8) + (-8)) + (-8)) = 8 => Even

Query 4 : abs(abs(-8)+4) = 12 => Even

Query 5 : abs(abs(abs(5) + 8 )+(-5)) =>8 => Even

Solutions

This is a typical use case for prefix sum. We calculate the running sum of all the elements and we answer the queries just by applying the prefix sum formula:

\( sum_i_j = PrefixSum[j] - PrefixSum[i-1] \)

That is, the sum between indexes \(i\) and \(j\) (inclusive) is calculated as the difference between the prefix sum at index \(\j) and the prefix sum at index \(i-1\).

Two notes:

  • the prefix sum is not simply calculated with addition because absolute value is applied on top.
  • in the code below, remember the indxing is 0-based

Here is an implementation of the presented idea in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int N, Q;
cin >> N >> Q;
vector<long long> prefix;
prefix.resize(N);
copy_n(istream_iterator<long long>(cin), N, begin(prefix));
partial_sum(begin(prefix), end(prefix), begin(prefix), [](int curr, int nxt){
   return abs(curr+nxt);
});
int L, R;
while (Q--)
{
    cin >> L >> R;
    auto num = (L==1) ? prefix[R-1] : (prefix[R-1]-prefix[L-2]);
    cout << (num%2 ? "Odd" : "Even") << endl;
}    
We've worked on this challenge in these gyms: modena 
comments powered by Disqus