adarsh000321's blog

By adarsh000321, history, 5 weeks ago, In English

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?

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have any idea about the solution? The solution should not exceed O(nlogn) or O(n*sqrt(n)).

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, sorry but I was not able to find that question. But now understood the solution and thanks for helping me out.