# Finding the largest of a series of numbers being XORed

I'm working on solving a problem involving finding the largest of a series of numbers being XORed.

This is the actual problem:

Xorq has invented an encryption algorithm which uses bitwise XOR operations extensively. This encryption algorithm uses a sequence of non-negative integers $x_1, x_2, ... x_n$ as key. To implement this algorithm efficiently, Xorq needs to find maximum value for ($a$ xor $x_j$) for given integers $a$, $p$ and $q$ such that $p<=j<=q$. Help Xorq to implement this function.

Input

First line of input contains a single integer $T$ ($1 <= T <= 6$). T test cases follow.

First line of each test case contains two integers $N$ and $Q$ separated by a single space ($1 <= N <= 100,000$; $1 <= Q <= 50,000$). Next line contains $N$ integers $x_1, x_2, ... x_n$ separated by a single space ($0 <= x_i < 2^{15}$). Each of next Q lines describe a query which consists of three integers $a_i$, $p_i$ and $q_i$ ($0 <= a_i < 2^{15}$, $1 <= p_i <= q_i <= N$).

Output

For each query, print the maximum value for ($a_i$ xor $x_j$) such that $p_i <= j <= q_i$ in a single line.

I keep failing because of a timeout. What are some ways in which I could optimize my code to reduce time?

Is there a better way to do the bit manipulation? Should I be using a different data structure than an array? I've read a few articles on optimization and changed a few things, but nothing that made a real difference. Maybe I need to attempt the problem in a different fashion?

#include <stdio.h>

int main (int argc, char * argv[]) {
unsigned int T,N,Q,i,a,p,q,count,max,n[100000],res[100000];
scanf ("%d\n%d %d", &T, &N, &Q);
while (T--) {
for (i = 0; i < N; i++) {
scanf ("%d", &n[i]);
}
while (Q--) {
count = 0;
scanf ("%d %d %d", &a, &p, &q);
p--;
q--;
for (i = p; i <= q; i++) {
res[count++] = a ^ n[i];
}
max = res[0];
for (i = count; i--;) {
if (res[i] > max) {
max = res[i];
}
}
printf ("%d\n", max);
}
}
return 0;
}


I apologize for all the arbitrarily named variables. All of these problems just use single character names as their variables.

-
I get a little lost with these. Are these values right for the sample test case? N=15, Q=8, x<sub>1</sub> to x<sub>15</sub> are 1 to 15. There are Q (8) lines after the x values. a<sub>i</sub>, p<sub>i</sub> and q<sub>i</sub> are on each of those lines? And p<sub>i</sub><=j<=q<sub>i</sub> means that you basically loop through the numbers from the second and third number on that line in you array of x elements and xor it with the first number on that line, then return the maximum result you get? – Jason Goemaat Jul 24 '14 at 19:17
Yes, that is correct. I used that for loop as an optimization for counting down to zero described on this site – Ryan McClure Jul 24 '14 at 19:20
No need to store the results in an array, you can just track the max in the loop. I get timeouts too, it seems to be only 2s. I downloaded sample 1 and it has 3 tests, each with N=100000 and Q=10000. I have an idea to speed it up by putting the numbers in a B-Tree at the start, based on most-significant bit... I might try that... It would be easier if the x numbers were unique, are they supposed to be? – Jason Goemaat Jul 24 '14 at 20:04
I don't think they can be, since 0 <= x <= 32,768 and there can be up to N=100000 of them. – Ryan McClure Jul 24 '14 at 20:10

What I ended up doing took at most 0.27s for trial #10. Since the maximum value is 32767, I just create an array with a structure that stores a list of indexes that have that value:

typedef struct {
int indexCount;
int *indexes; // position (i.e. j) where number is
} NODE;


Then in my loop, I loop down from the largest possible value to 0, xor it with 'a' to get the value of x to look for. That is the index into the array of nodes and will tell me quickly which indexes (x1..xN) contain that number.

for (largest = 32767; largest > 0; largest--) {
v = largest ^ a; // value we're looking for
// see if it has any indexes in range
for (k = 0; k < nodes[v].indexCount; k++) {
index = nodes[v].indexes[k];
if (index >= p && index <=q) {
found = 1;
break;
}
}
if (found)
break;
}
printf("%d\n", largest);


This has a couple of notes:

1. It does more work up front so the number of tests are affected less
2. It's only viable because of the restriction in values for x and a (0<=xi<=215 and 0<=ai<=215). If the possible values were 231 it could loop 2 billion times.
3. It works fastest when the final results are larger. A random sampling of values in the possible range should be fine but could slow down if the requested range has none of those values. The poorest results would be a large list of x values that match a (giving a result of 0)

I think a better solution would be a tree where left means the number has a '0' at that bit and right means the number has a '1' at that bit. The leaves would be the x values following that bit pattern. Each node would maintain the index range where numbers below could be found. You would walk down the tree using the opposite of bits in the a value from bit 14 down as long as the node's index range overlaps with p..q. Structure:

typedef struct {
int indexCount;
int capacity;
int *indexes;
} INDEXLIST;

typedef struct {
NODE *left, *right;
int minIndex, maxIndex;
INDEXLIST indexes;
} NODE;


When you finally reach the bottom with all 14 bits chosen, those bits make up the number and indexes in the node is the list of indexes.

edit

I implemented the list (ideone) if anyone's interested, gotta practice c when I can...

typedef struct {
int count;
int capacity;
int *indexes; // position (i.e. j) where number is
} INDEXLIST;

typedef struct NODE_STRUCT {
struct NODE_STRUCT *left, *right;
int minIndex, maxIndex;
int value; // for a leaf
INDEXLIST *indexList; // for a leaf
} NODE;


So when loading the x1..xN, I populate the tree starting at bit 14 and going left for a 0 and right for a 1, expanding minIndex and maxIndex for all the nodes in the path and only populating value and indexList for the final node.

When searching for a maximum value, I traverse the tree in the order of looking for the highest resulting xored value. For instance if bit 14 of the a value is 1, I go left first looking for x values with a 0 in that position. If bit 13 is 0, I then go right first looking for an x with a 1 in that position. It traverses the tree in the order to maximize the resulting xored value, so when I reach a leaf that contains an index in range, I return the value I've built-up based on those left-right choices which will be the original inserted value xored with the a value passed.

NODE *add_index_to_node(NODE *node, int index, int value, int depth);
int find_largest(NODE *node, int value, int minIndex, int maxIndex, int depth);

while (T--) {
scanf("%d %d", &N, &Q);
for (i = 1; i <= N; i++) {
scanf("%d", &x);
root = add_index_to_node(root, i, x, 0);
}

for (i = 0; i < Q; i++) {
scanf("%d %d %d", &a, &p, &q);
result = find_largest(root, a, p, q, 0);
printf("%d\n", result);
}

// free memory
free_node(root);
root = NULL;
}


A unique value could have 96+ bytes of overhead not including the other tree nodes, but it could handle more bits with just recompiling and is a lot more efficient at sparse lists than my first try...

-
Great answer! Just one question: how are you loading up the array of structs originally? – Ryan McClure Jul 24 '14 at 23:24
Zeroing them out, then for each x value read on the second line, I add the index to nodes[x], allocating memory and copying the old indexes array and adding the index to the end, then increment indexCount. – Jason Goemaat Jul 24 '14 at 23:30

The (p,q) range could be huge, yet it may yield at most 216 distinct results. To gain speed you have to avoid recalculations.

You need an aux data structure to quickly tell if a given X appears in a given (p,q) range. Then you can answer each query in a constant time:

unsigned max = 0;
for (int x = 0; x < 215; ++x) {
if (appears(x, p, q) {
unsigned result = x ^ a;
if (result > max) {
max = result;
}
}
}


There are various approaches for such structure. An interval tree comes to mind first. Or you may consider a 216-entry array of subarrays, where each subarray contains indices of a given X. Or something entirely different. I don't have an answer which one suits the problem best. Study and experiment.

-
Thanks, I'll definitely give it a try! I realized when the question was pasted, it turned 2^15 into 215 so it's really much larger. I imagine your idea would still make a difference though? – Ryan McClure Jul 24 '14 at 19:51
I was wondering what a strange number 215 is. Anyway I guess the point is still valid. – vnp Jul 24 '14 at 20:59

Putting all variables of the same type onto a single line can be bad for readability and maintenance:

unsigned int T,N,Q,i,a,p,q,count,max,n[100000],res[100000];


Since the single-character variables are similar, they can still be together. The rest of them, however, should be on separate lines. Also, since i is a loop counter, it's best to declare it as close as possible to its for loop instead.

unsigned int T, N, Q, a, p, q;
unsigned int count;
unsigned int max;
unsigned int n[100000]
unsigned int res[100000];

-
Thanks for the suggestion, I typically make it more readable but am trying to figure out a way to increase the speed of the code. I may have been unclear about that. – Ryan McClure Jul 24 '14 at 19:36
@RyanMcClure: I know. On Code Review, advice on any aspect of the code is allowed, not just what's requested. There are many people on this site who can give great help on the performance. – Jamal Jul 24 '14 at 19:37
Ah alright, got it, thanks! – Ryan McClure Jul 24 '14 at 19:39