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?
Does anyone have any idea about the solution? The solution should not exceed O(nlogn) or O(n*sqrt(n)).
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.
Thanks rath772k for the explanation.
I am not able to catch this fact , can you elaborate
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
Hi, sorry but I was not able to find that question. But now understood the solution and thanks for helping me out.