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

Subarray with XOR less than k
Автор wish_me, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

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

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

→ Ответить
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to find the xor of all such subarrays?

→ Ответить