Tag Archives: powers

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).