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:
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]
|
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
|
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)
})
}
|