# 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 prefix; prefix.resize(N); copy_n(istream_iterator(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