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")
}