Can anyone help with this tricky xor question

Правка en2, от jatinxkirito, 2024-05-09 17:43:57

Can any one help with this question

Given array arr of length n, we define function f(arr) as, if n = 1, f(arr) = arr[1] else, f(arr) = f(arr[1] ^ arr[2], arr[2] ^ arr[3],..., arr[n-1] ^ arr[n]) where, is bitwise XOR operator For example, arr = [1, 2, 4, 8], n = 4 f(1, 2, 4, 8) = f(1^2, 2^4, 4^8) = f(3, 6, 12) = f(3^6, 6^12) = f(5, 10) = f(5^10) = f(15) = 15

You need to answer q queries, each query you are given two integers / and r. For each, what is the maximum of f for all continuous subsegments of the array arrı, arrı+1,..., arrr.

Sample Testcase Input n = 6 arr = [1, 2, 4, 8, 16, 32] q = 3 queries = [ [1, 3], [2, 5], [1,6] ] Output [6,30,60]

Explanation

For query [1,3], the possible continuous segments are, [1], [2], [4], [1,2]. [2.4] and [1,2,4] f(1)=1, f(2)= 2, 1(4) = 4, f(1,2)=f(1^2) = 3 f(2,4)=f(2^4) = 6 f(1,2,4)=f(1^2, 2^4) = f(3,6) = 5 max(1,2,4,3,5,5) = 6 = Output For query [2,5], the possible continuous segments are,

[2], [4], [8], [16], [2,4], [4,8], [8,16], [2,4,8], [4,8,16], [2,4,8,16] f(2)= 2, f(4) = 4, f(8) = 8, f(16) = 16 f(2,4) = f(2^4) = 6 f(4,8) = f(4^8) = 12 f(8,16) = f(8^16) = 24 f(2,4,8) = f(6^12) = 10 f(4,8,16) = f(4^8, 8^16) = f(12, 24) = 20 f(2,4,8,16) = f(2^4, 4^8, 8^16) = f(6, 12, 24) = f(6^12, 12^24) = f(10, 20) = 30 max(2,4,8,16,6,12,24, 1,20,30) = 30 = Output

Similarily for the query [1,6] we can observe that the maximum value is obtained for the subsegment [3,6] i.e [4,8,16,32] = 60.

Constraints: 1 <= n <= 5000, 0 <= arr[i] <= 2^30-1, 1<=q<=1e5

Теги xor, range

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский jatinxkirito 2024-05-09 17:43:57 13
en1 Английский jatinxkirito 2024-05-09 17:38:22 1607 Initial revision (published)