Databases
StackOverflow2013
Postsdbo
POmaximum value of xor operation
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POmaximum value of xor operation
    primarykey
    data
    text
    <p>I came up with this question.</p> <blockquote> <p>There is an encryption algorithm which uses bitwise XOR operations extensively. This encryption algorithm uses a sequence of non-negative integers x<sub>1</sub>, x<sub>2</sub>, ... x<sub>n</sub> as key. To implement this algorithm efficiently, Xorq needs to find maximum value for (a xor x<sub>j</sub>) for given integers a, p and q such that p &lt;= j &lt;= q. Help Xorq to implement this function.</p> <h3>Input</h3> <p>First line of input contains a single integer T (1&lt;=T&lt;=6). T test cases follow.</p> <p>First line of each test case contains two integers N and Q separated by a single space (1 &lt;= N &lt;= 100,000; 1 &lt;= Q &lt;= 50,000). Next line contains N integers x<sub>1</sub>, x<sub>2</sub>, ... x<sub>n</sub> separated by a single space (0 &lt;= x<sub>j</sub> &lt; 215). Each of next Q lines describe a query which consists of three integers a<sub>i</sub>, p<sub>i</sub> and q<sub>i</sub> (0 &lt;= a<sub>i</sub> &lt; 215, 1&lt;= p<sub>i</sub> &lt;= q<sub>i</sub> &lt;= N).</p> <h3>Output</h3> <p>For each query, print the maximum value for (a<sub>i</sub> xor x<sub>j</sub>) such that p<sub>i</sub> &lt;= j &lt;= q<sub>i</sub> in a single line.</p> <h3>Sample Input</h3> <pre><code>1 15 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 6 10 1023 7 7 33 5 8 182 5 10 181 1 13 5 10 15 99 8 9 33 10 14 </code></pre> <h3>Sample Output</h3> <pre><code>13 1016 41 191 191 15 107 47 </code></pre> <h3>Explanation</h3> <pre><code>First Query (10 6 10): x6 xor 10 = 12, x7 xor 10 = 13, x8 xor 10 = 2, x9 xor 10 = 3, x10 xor 10 = 0, therefore answer for this query is 13. Second Query (1023 7 7): x7 xor 1023 = 1016, therefore answer for this query is 1016. Third Query (33 5 8): x5 xor 33 = 36, x6 xor 33 = 39, x7 xor 33 = 38, x8 xor 33 = 41, therefore answer for this query is 41. Fourth Query (182 5 10): x5 xor 182 = 179, x6 xor 182 = 176, x7 xor 182 = 177, x8 xor 182 = 190, x9 xor 182 = 191, x10 xor 182 = 188, therefore answer for this query is 191. </code></pre> </blockquote> <p>I tried this by first making the numbers length(in binary) in the given range equal and then comparing 'a' bit by bit with the particular xj values.But it is time exceeding. Maximum time limit in java is 5sec.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USSiva Krishna Aleti
    1. USSiva Krishna Aleti
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POmaximum value of xor operation
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POmaximum value of xor operation
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    3. VO
      singulars
      1. POmaximum value of xor operation
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    1. CO*"Xorq needs to find maximum value for (a xor xj) for given integers a,p and q such that p<=j<=q."* What's Xorq? What's xj?
      singulars
      1. POmaximum value of xor operation
      1. USm0skit0
    2. COIf you want to make things as slow as possible, by all means do math with strings.
      singulars
      1. POmaximum value of xor operation
      1. USharold
    3. COWhere is your question?
      singulars
      1. POmaximum value of xor operation
      1. USIshtar
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload