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