# Problem Link:

**Author**: Roman Rubanenko

**Tester/Editorialist**: Utkarsh Lath

# Difficulty:

Cakewalk

# Pre-requisites:

understanding of bitwise operators

# Problem:

Given a list of numbers **A**, and integers **K**, **Ans**, and function **op**, predict the outcome of following function

```
int F(K, Ans, op, A[N])
for i=1 to K
for j=1..N
Ans = (Ans op A[j])
return Ans
```

**op** can be either **XOR**, **AND**, or **OR**.

# Explanation:

Lets first try to see what is the complexity of the above function. The outer loop runs **K** times and inner loop runs **N** times, giving **O(N**K)**. Since **K ≤ 10 ^{9}, N ≤ 1000**, doing it naively can take upto

**10**instructions, which will time out.

^{12}If we think about it, the final answer can be written down as:

Ans

opA[1]opA[2]op…opA[N]opA[1]opA[2]op…opA[N] … K times …

Using associativity of The operators, if **M** is the result of applying all operators once, then

M = A[1]

opA[2]op…opA[N]

Ans = AnsopMopMop…K times…opM

However,

M

ANDM = M

MORM = M

MXORM = 0

Therefore, K can be totally eliminated from our complexity, because

- If
**op**is either**AND**or**OR**, then for**K > 0**,

M

opMop…K times…opM = M

- If
**op**is**XOR**, then

M

opMop…K times…opM = M if K is odd, 0 otherwise.

The final solution would be

```
int FFast(K, Ans, op, A[N])
if (op is XOR)
K = K%2
else
K = min(K, 1)
return F(K, Ans, op, A)
```