# Hackerrank Solution: Even Odd Query

Original Problem

You are given an array $$A$$ of size $$N$$. You are also given an integer $$Q$$. Can you figure out the answer to each of the $$Q$$ queries?

Each query contains 2 integers $$x$$ and $$y$$, and you need to find whether the value find(x, y) is Odd or Even:

find(int x,int y) {
if(x>y) return 1;
ans = pow(A[x],find(x+1,y))
return ans
}

Note: pow(a, b) = $$a^b$$.

## Input Format

The first line of the input contains an integer $$N$$. The next line contains $$N$$ space separated non-negative integers (whole numbers less than or equal to 9).The line after that contains a positive integer, $$Q$$ , the denotes the number of queries to follow. $$Q$$ lines follow, each line contains two positive integer $$x$$ and $$y$$ separated by a single space.

## Output Format

For each query, display 'Even' if the value returned is Even, otherwise display 'Odd'.

## Constraints

• 2 ≤ N ≤ 105
• 2 ≤ Q ≤ 105
• 1 ≤ x,y ≤ N
• x ≤ y

The array is 1-indexed.

No 2 consecutive entries in the array will be zero.

## Solution

When analyzing the recurrence, we can see that the function calculates the continues exponentiation of the array elements, beginning with $$x$$ up to $$y$$:

$a_x^{⋰^{{a_{y-k}^{⋰^{a_{y-1}^{a_y}}}}}}$

From it, it is clear that we can state the algorithm in a non-recursive manner:

function find(arr, x, y) {

let e = 1;
while (x <= y) {
e = Math.pow(arr[y], e);
y--;
}
return e;
}

But looping is not necessary, since we want to know if the result is even or odd, which is

$a^b\bmod{2} \equiv \begin{cases} 1 &\text{if } b=0 \\a\bmod{ 2} & \text{else} \end{cases}$

That means that except the special case $$b=0$$, we can ignore the exponent completely. With this knowledge, the only remaining part is $$a_x \bmod{2}$$.

What we still have to investigate on is the case that $$b=0$$. $$b$$ can only be zero if $$a_{x+1}=0$$ and $$x\neq y$$. If $$a_{x+2}$$ would be $$0$$, $$a_{x+1}$$ would be $$1$$, so we don't have to go further. But of course, if $$x=y$$, we have $$a_x^{a_x}$$ and it does not matter if the next array element is zero for that query. Case $$0^0$$ can be ignored, since the problem statement promises no 2 consecutive zeros in the array.

The problem statement says $$x\leq y < N$$, but we require $$x\neq y$$, from which follows that $$x<y$$. Another thing we should keep track of is that $$x + 1 < N$$, to avoid out of bound index access. Collecting all these information leads to

$x + 1 < N \land x < y \land x \leq y < N \Rightarrow x + 1 \leq y \Leftrightarrow x<y$

The final solution is then

function find(A, x, y) {

if (x < y && A[x + 1] == 0)
return 1;
return A[x] % 2;
}

function solve(arr, queries) {

return queries.map(([x, y]) => find(arr, x - 1, y - 1) ? "Odd" : "Even")
}

« Back to problem overview