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

Solutions

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<i32> = lines
        .next()
        .unwrap()
        .split(' ')
        .map(|x| x.parse().unwrap())
        .collect();

    let queries: Vec<(usize, usize)> = lines
        .map(|query_str| {
            let q: Vec<usize> = query_str.split(' ').map(|x| x.parse().unwrap()).collect();
            (q[0], q[1])
        })
        .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<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;
}

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<i32> for Parity {
    fn from(n: i32) -> Self {
        if n & 1 == 1 {
            Parity::Odd
        } else {
            Parity::Even
        }
    }
}

fn solve<N, Q>(numbers: N, queries: Q) -> impl Iterator<Item = Parity>
where
    N: IntoIterator<Item = i32>,
    Q: IntoIterator<Item = (usize, usize)>,
{
    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<i32> = lines
        .next()
        .unwrap()
        .split(' ')
        .map(|x| x.parse().unwrap())
        .collect();

    let queries = lines.map(|query_str| {
        let q: Vec<usize> = query_str.split(' ').map(|x| x.parse().unwrap()).collect();
        (q[0], q[1])
    });

    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<N, Q>(numbers: N, queries: Q) -> impl Iterator<Item = Parity>
where
    N: IntoIterator<Item = i32>,
    Q: IntoIterator<Item = (usize, usize)>,
{
    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 
comments powered by Disqus