Блог пользователя adarsh000321

Автор adarsh000321, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится 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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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