understanding of bitwise operators
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.
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(NK)**. Since K ≤ 109, N ≤ 1000, doing it naively can take upto 1012 instructions, which will time out.
If we think about it, the final answer can be written down as:
Ans op A op A op … op A[N] op A op A op … op A[N] … K times …
Using associativity of The operators, if M is the result of applying all operators once, then
M = A op A op … op A[N]
Ans = Ans op M op M op …K times… op M
M AND M = M
M OR M = M
M XOR M = 0
Therefore, K can be totally eliminated from our complexity, because
- If op is either AND or OR, then for K > 0,
M op M op …K times… op M = M
- If op is XOR, then
M op M op …K times… op M = 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)