wish_me's blog

Subarray with XOR less than k
By wish_me, history, 7 years ago, In English

I need help in this problem.Can any one explain.Thanks in advance.

Given an array of n numbers and a number k. You have to write a program to find the number of subarrays with xor less than k.

Examples:

Input: arr[] = {8, 9, 10, 11, 12}, k=3 Output: 4 Sub-arrays [1:3], [2:3], [2:5], [4:5] have xor values 2, 1, 0, 1 respectively.

Input: arr[] = {12, 4, 6, 8, 21}, k=8 Output: 4

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

Comments Comments (5)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Let p[i] = a1 ^ a2 ^ a3 ^ ... ^ ai. Now xor of subarray (l, r] is p[r] ^ p[l].
If O(N^2) is fine, you can just use two for's to calculate it.
If it isn't you can solve it O(N * log(max_ai)),if you use trie to calculate it.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't this your problem? http://www.spoj.com/problems/SUBXOR/

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to find the xor of all such subarrays?

→ Reply