By adarsh000321, history, 12 months ago,

Note: This problem has been asked in one of the online coding challenges.

Given an array A of size N. You are asked Q queries. There will be two types of queries:

1 L R K: Print “Yes” if the subarray A[L, R] can be split into K contiguous subarrays such that each of these K subarrays have a subarray XOR with odd number od set bits. Otherwise, print “No”.

2 L X: Update A[L] = X .

Constraints: 1 <= A[i] <= 1e9 1 <= L, R, K <= N 1 <= N, Q <= 1e5

Can anyone give me some idea about how to solve this problem?

• -3

 » 12 months ago, # |   0 Does anyone have any idea about the solution? The solution should not exceed O(nlogn) or O(n*sqrt(n)).
 » 12 months ago, # |   +3 Let $p$ be the number of set bits of some number $x$ and let there be a number $y$ with an even number of set bits. Let $x \oplus y$ have $q$ number of set bits. $p$ and $q$ will have the same parity. Similarly, if $y$ has an odd number of set bits, $p$ and $q$ will have different parity. This fact leads us to the solution. Count the number of elements in $L$ to $R$ having an odd number of set bits. If this number is of the form $k+2i, i \geq 0$, answer is $Yes$ else $No$. Point update and range queries for counting the number of elements with an odd number of set bits. can be easily handled using segment trees.
•  » » 12 months ago, # ^ |   0 Thanks rath772k for the explanation.
 » 12 months ago, # |   0 Someone actually wrote a question about this yesterday. Essentially, you just check the parity of the bitcount in a subarray, and you only care about the number of odd bit counts you have in that subrange.Even ^ Even = Even Odd ^ Odd = Even Even ^ Odd = Odd
•  » » 12 months ago, # ^ |   0 Hi, sorry but I was not able to find that question. But now understood the solution and thanks for helping me out.