MINIAND ENIGMA Editorial

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

Author solution

Author’s Solution