# 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 paity (Odd/Even) of 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 2 : 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

## O(N x Q) Solution

A naive solution is to calculate the sum linearly from $$i$$ to $$j$$ for each query.

Haskell. For each query, it folds elements from i to j included.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  doQuery :: [Int] -> (Int, Int) -> String doQuery numbers (from, to) = if odd $foldl (\a n -> (abs a) + n) x xs then "Odd" else "Even" where x:xs = take (to - from + 1)$ drop (from - 1) numbers solve :: ([Int], [(Int, Int)]) -> [String] solve (numbers, queries) = (doQuery numbers) <$> queries parseQuery :: String -> (Int, Int) parseQuery queryStr = (read a, read b) where [a, b] = words queryStr parse :: String -> ([Int], [(Int, Int)]) parse input = (num, queries) where numStr:queriesStr = tail$ lines input num = read <$> words numStr :: [Int] queries = parseQuery <$> queriesStr :: [(Int, Int)] main = interact \$ unlines . solve . parse 

Rust solution.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27  fn main() { use std::io::{self, BufRead}; let stdin = io::stdin(); let mut lines = stdin.lock().lines().map(Result::unwrap).skip(1); let numbers: Vec = lines .next() .unwrap() .split(' ') .map(|x| x.parse().unwrap()) .collect(); let queries: Vec<(usize, usize)> = lines .map(|query_str| { let q: Vec = query_str.split(' ').map(|x| x.parse().unwrap()).collect(); (q, q) }) .collect(); for (from, to) in queries { let slice = &numbers[from-1..to]; let x : i32 = slice.iter().fold(0, |acc, n| acc.abs() + n); println!("{}", if x & 1 == 1 { "Odd" } else { "Even" }); } } 

## O(N) Solution

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 indexing 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; } 

Rust. This solution uses iterators to avoid keeping in memory the queries array. We also created a new type Paity to express the solution without needing to return a string.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57  #[derive(Debug)] enum Parity { Odd, Even, } impl From for Parity { fn from(n: i32) -> Self { if n & 1 == 1 { Parity::Odd } else { Parity::Even } } } fn solve(numbers: N, queries: Q) -> impl Iterator where N: IntoIterator, Q: IntoIterator, { let sums: Vec<_> = numbers .into_iter() .scan(0i32, |acc, n| { *acc = (*acc + n).abs(); Some(*acc) }) .collect(); queries.into_iter().map(move |(from, to)| { let l = if from == 1 { 0 } else { sums[from - 2] }; let r = sums[to - 1]; Parity::from(r - l) }) } fn main() { use std::io::{self, BufRead}; let stdin = io::stdin(); let mut lines = stdin.lock().lines().map(Result::unwrap).skip(1); let numbers: Vec = lines .next() .unwrap() .split(' ') .map(|x| x.parse().unwrap()) .collect(); let queries = lines.map(|query_str| { let q: Vec = query_str.split(' ').map(|x| x.parse().unwrap()).collect(); (q, q) }); solve(numbers, queries).for_each(|v| println!("{:?}", v)); } 

## Other optimizations

We can avoid abs, because we just need the parity, which isn’t influenced by the number sign. We can even avoid the sum and just use the xor, preventing possible integer overflow.

Solution by Enrico Lovisotto

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  N, Q = map(int, input().split()) v = list(map(lambda x: x % 2 != 0, map(int, input().split()))) cumsum = [True] for element in v: cumsum.append(cumsum[-1] ^ element) for _ in range(Q): start, stop = map(int, input().split()) if cumsum[stop] ^ cumsum[start-1]: print('Odd') else: print('Even') 

We can even avoid checking if start == 1 if we add a 0 at the beginning.

This is the Rust program above with these optimizations:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  fn solve(numbers: N, queries: Q) -> impl Iterator where N: IntoIterator, Q: IntoIterator, { let mut acc = 0; let sums: Vec<_> = once(0) .chain(numbers.into_iter().map(|n| { acc = acc ^ n; acc })) .collect(); queries.into_iter().map(move |(from, to)| { let l = sums[from - 1]; let r = sums[to]; Parity::from(r ^ l) }) } 
We've worked on this challenge in these gyms: modena  milan  padua