PROBLEM LINK:
MINIAND - Minion AND Range ENIGMA-Plinth’20
Author - tds115
Editorialist - Priyam Khandelwal
DIFFICULTY:
Easy
PREREQUISITES:
Prefix sums, Bitwise AND
PROBLEM:
Given an array, find whether Bitwise AND of a range A[L], A[L+1], ... A[R] is even or odd.
Explanation
The main observation here is that if there is atleast one even number in the required range, answer will be even (Think why?).
To solve the reduced problem of finding whether there is an even number in the range, make a prefix array which will tell number of even numbers upto index i. Then for each query calculate pre[R] - pre[L-1]. If the value is greater than 0 then the answer is “EVEN” else the answer is “ODD”.