Поиск двух элементов, XOR которых максимальный

Question

У меня возникла проблема, требующая от меня найти элемент из заданного массива целых чисел, XOR которого является максимальным с заданным номером.

Пример:

А [] = {2,7,3,6}; Номер = 4.

Теперь 2^4 = 6, 7^4 = 3, 3^4 = 7, 6^3 = 2. Следовательно, 3 должен быть ответом, поскольку 3^7 является максимумом.

Я пытаюсь следовать структуре, подобной trie, и продолжать находить максимальный результат по битам, то есть начиная с MSB, если мой бит равен 1, тогда я пересекаю сторону 0, а если мой бит равен 0 , то я пересекаю 1 сторону узла. Я придумал следующий код.

#include<iostream> 
#include<cstdio> 
#include<cmath> 
#include<string> 
#include<cstring> 
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<list> 
#include<queue> 
#include<cstdlib> 
#include<numeric> 
#include<set> 
#include<map> 
#include<deque> 
#include<climits> 
#include<cassert> 
#include<cctype> 
#include<ctime> 
#include<iterator> 
#include<iomanip> 
#include<functional> 
#include<fstream> 
#include<ostream> 
#include<istream> 
#include<sstream> 
using namespace std; 

#define sf(n)    scanf("%d",&n) 
#define pf(n)    printf("%d",n)   
#define pfln(n)    printf("%d\n",n)   

#define vi     vector <int > 
#define pb     push_back() 
#define debug(n)    printf("n = %d\n",n) 
#define PI 3.14159265358979 
#define LL 1000000007 

int ans[32]; 

class TrieNode{ 
    public: 
     int bit; 
     bool end; 
     TrieNode *child[2]; 
     TrieNode(int val){ 
      this->bit = val; 
      this->end = false; 
      this->child[0] = NULL; 
      this->child[1] = NULL; 
     } 
}; 
void addWord(TrieNode *node,int n){ 
    int a[32]; 
    int bin[32]; 
    int m = n; 
    int j = 0; 
    //cout<<"in adding\n"; 
    while(m>0){ 
     a[j++] = m%2; 
     m/=2; 
    } 
    for(int i = j-1,k=0 ; i>=0 ; k++,i--){ 
     bin[32-i-1] = a[i]; 
    } 
    for(int i = 0 ; i < 32-j ; i++){ 
     bin[i] = 0; 
    } 
    for(int i = 0 ; i < 32 ; i++) 
     cout<<bin[i]; 
    for(int i = 0 ; i < 32 ; i++){ 
     if(node->child[bin[i]] == NULL){ 
      TrieNode *tmp = new TrieNode(bin[i]); 
      node->child[bin[i]] = tmp; 
      node = node->child[bin[i]]; 
     } 
     else{ 
      node = node->child[bin[i]]; 
     } 
    } 
    node->end = true; 

} 

void findmax(TrieNode *node, int q){  
    int a[32];int j = 0; 
    int bin[32]; 
    while(q>0){ 
     a[j++] = q%2; 
     q/=2; 
    } 
    for(int i = j-1,k=0 ; i>=0 ; k++,i--){ 
     bin[32-i] = a[i]; 
    } 
    for(int i = 0 ; i < 32-j ; i++){ 
     bin[i] = 0; 
    } 
    for(int i = 0 ; i < 32 ; i++){ 
     if(node->child[0]->bit == bin[i] && node->child[1]!=NULL){ 
      ans[i] = node->child[1]->bit; 
      node = node->child[1]; 
     } 
     else if(node->child[1]->bit == bin[i] && node->child[0]!=NULL){ 
      ans[i] = node->child[0]->bit; 
      node = node->child[0]; 
     } 
     else{ 
      ans[i] = node->child[0] == NULL?node->child[1]->bit:node->child[0]->bit; 
      node = node->child[0] == NULL?node->child[1]:node->child[0]; 
     } 
    } 
} 
int main() 
{ 
    std::ios_base::sync_with_stdio(false); 
    TrieNode *root = new TrieNode(-1); 
    addWord(root,2); 
    addWord(root,7); 
    addWord(root,3); 
    addWord(root,6); 
    findmax(root,4); 
    for(int i = 0 ; i < 32 ; i++){ 
     cout<<ans[i]; 
    } 
    return 0; 
} 

Но я продолжаю получать ошибку сегментации и не могу запустить программу. Я пробовал каждый трюк для отладки кода, но я не могу понять проблему. Помогите найти причину ошибки времени выполнения.

Благодаря

Answer 1

Допустим, вы должны были найти максимум в массиве. Вы бы сделали примерно следующее:

int A[] = {2,7,3,6}; 
int maximum = std::numeric_limits<int>::min(); 
for(int i = 0; i < 4; ++i) 
    if(A[i] > maximum) maximum = A[i]; 

Что вам нужно сделать, это заменить условие.

for(int i = 0; i < 4; ++i) 
    if(func(A[i]) > maximum) maximum = A[i]; 

Где func() это функция, которая может выглядеть следующим образом:

int func(int x) 
{ 
    return x^4; 
} 

Конечно, это фиктивная реализация, вы могли бы пройти 4 в качестве параметра, например, но я надеюсь, что вы получили идея.

С другой стороны, вы могли бы использовать std::max_element(), чтобы сделать это:

int A[] = {2,7,3,6}; 
int maximum = std::max_element(std::begin(A), std::end(A), [](int const a, int const b){return func(a) < predicate(b)}); 

(. Где func() та же функция показать выше)