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.InputFirst 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\$).OutputFor 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.
Finding the largest of a series of numbers being XORed
optimization;performance;c;programming challenge;bitwise
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:It does more work up front so the number of tests are affected lessIt'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.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.editI 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...