algorithm - xor after applying filters on an array -

we have original array , list of filters each filter consists of indices allowed through filter. filters rather nice, e.g. grouped each power of 2 in following way (the filters upto n = 20).

• 1 (2^0) = 1 3 5 7 9 11 13 15 17 19
• 2 (2^1) = 1 2 5 6 9 10 13 14 17 18
• 4 (2^2) = 1 2 3 4 9 10 11 12 17 18 19 20
• 8 (2^3) = 1 2 3 4 5 6 7 8 17 18 19 20

i hope idea. apply or of these filters (user dictates filters apply) original array , xor of elements of transformed array answer. take example if original array have been [3 7 8 1 2 9 6 4 11] e.g. n = 9 , needed apply filters of 4, 2 , 1, transformations this.

• after applying filter of 4 - [3 7 8 1 x x x x 11]
• after applying filter of 2 - [3 7 x x x x x x 11]
• after applying filter of 1 - [3 x x x x x x x 11]

now xor of 3 , 11 e.g. 8 answer. can solve o(n * no. of filters) time, need better solution might give answer in o(no of filters) time. there way take advantage of properties of xor and/or pre-compute results , give answer filters. because there many queries filters, need answer queries in o(no of filters) time. kind of appreciated.

it can done in o(m) m number of items pass filters (independent of number of filters) iterating on array in particular way, generating indexes pass filters.

this easier see if write down examples starting @ zero:

• 1: 0 2 4 6 8 10 12 14 16 18 (numbers don't contain 1)
• 2: 0 1 4 5 8 9 12 13 16 17 (numbers don't contain 2, etc)
• 4: 0 1 2 3 8 9 10 11 16 17 18 19
• 8: 0 1 2 3 4 5 6 7 16 17 18 19

the filters constraint on bits of indexes in array. constraint of form index & filters = 0, filters sum of individual filters (eg 1 + 2 + 4 = 7). given valid index i next valid index i' can computed primitive operations: i' = (i | filters) + 1 & ~filters. idea here set bits filtered 0 +1 carry through them, filtered bits cleared again make index valid. total effect unfiltered bits incremented , filtered bits stay zero.

this gives simple algorithm iterate directly on valid indexes. start @ 0 (which valid) , increment using rule above until end of array reached:

for (int = 0; < n; = (i | filters) + 1 & ~filters)     // array[i], xor them