# Hackerrank Weekly #5 / problem 1

A quick post on the first problem from Hackerrank Weekly #5.

After a quick analysis of the problem statement, you can reformulate it in the following way:

You're given the array $A[1..n]$.

After that, there are $q$ queries. For each query $(i, j)$ you have to print the parity of the following formula:

$pow(a_i, pow(a_{i+1}, \ldots, pow(a_j, 1) \ldots )$,

where

$pow(x, k) := x^k$

Let's take a query $(i, j)$. In order to decide the parity for that query, you have to decide what's the parity of $a_i$ raised to some power $p$.

For any $p > 0$, it's sufficient to check the parity of $a_i$, because if $a_i$ is even, then after raising to any positive $p$ it's still even and if $a_i$ is odd, then after raising to any positive $p$ it remains odd.

The only other case is when $p = 0$ (it's guaranteed that there are no two adjacent 0 in the array $A$, so $0^0$ never happens).

We can observe that $p = 0$ if and only if $a_{i + 1} = 0$. If that's the case then parity of $a_i$ doesn't matter and the result is always odd, because we raise a non negative number to $0$-th power.

The time complexity of that method is $O(n + q)$.