Finding the largest of a series of numbers being XORed

Question

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.

Answer 1

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 (x₁..x_N) 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<=x_i<=2¹⁵ and 0<=a_i<=2¹⁵). If the possible values were 2³¹ 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 x₁..x_N, 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...

Answer 2

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];

Answer 3

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.

Answer 4

As written, the code can't work unless T is 1. There are supposed to be different N and Q for each test case.

The lines:

    scanf ("%d\n%d %d", &T, &N, &Q);
    while (T--) {

might work as:

    scanf ("%d\n", &T);
    while (T--) {
        scanf ("%d %d", &N, &Q);

As for optimizing: eliminate the res array. Just accumulate the maximum as you go, in one pass. And you are guaranteed at least one test, so you could start with max=0 and do the tests from p to q. This won't actually save much time, but I think it is about all you can reasonably expect to improve. It will save memory.