0

I am facing a problem that needs me to find an element from a given array of integers whose XOR is maximum with a given number.

Example :

A[] = {2,7,3,6}; Number = 4.

Now, 2^4 = 6 , 7^4 = 3 , 3^4 = 7, 6^3 = 2. Hence, 3 should be the answer as 3^7 is the maximum.

I'm trying to follow a trie like structure and keep on finding the maximum result possible bit by bit i.e. starting from MSB, if my bit is 1, then I traverse down the 0 side, and if my bit is 0, then I traverse down the 1 side of the node. I have come up with the following code. 

#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;
 }

But I'm keep on getting a segmentation fault and can't run the program. I have tried every trick to debug the code but I can't figure out the problem. Please help in finding the cause of runtime error.

Thanks

4

1 に答える 1

0

配列の最大値を見つけなければならないとしましょう。次のようにします。

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()は上記と同じ機能です。）

于 2015-10-19T21:40:29.453 に答える