maximum xor of two number in an array using c(used trie data structure)
Vikram Shaw
138
Bit ManipulationTrie

This is the link of the question.
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
This solution runs well in my system but when i try to run it in leetcode environment, giving me runtime error.

Line 15: Char 23: runtime error: member access within misaligned address 0xbebebebebebebebe for type 'struct Trie', which requires 8 byte alignment (solution.c) 0xbebebebebebebebe: note: pointer points here 

struct Trie
{
	struct Trie *one,*zero;
	int val,tf;
}*root=NULL;

void insert(int data)
{
	int j=1<<30;
	int i;
	struct Trie *pointer=root;
	for(i=0;i<31;i++)
	{
		int bit = (data & j) == 0 ? 0 : 1;
		if(bit==0 && pointer->zero==NULL)
		{
			struct Trie *tree=(struct Trie*)malloc(sizeof(struct Trie));
			tree->tf=0;
			pointer->zero=tree;
		}
		if(bit==1 && pointer->one==NULL)
		{
			struct Trie *tree=(struct Trie*)malloc(sizeof(struct Trie));
			tree->tf=0;
			pointer->one=tree;
		}
		pointer=bit==0?pointer->zero:pointer->one;
		j>>=1;
	}
	pointer->val=data;
	pointer->tf=1;
}

void createTrie(int* arr,int n)
{
	root=(struct Trie*)malloc(sizeof(struct Trie));
	root->zero=root->one=NULL;
	root->tf=0;
	int i;
	for(i=0;i<n;i++)
		insert(arr[i]);
}

int max(int a,int b)
{
	return a>b?a:b;
}

int get(struct Trie* one,struct Trie* zero)
{
	if(one->tf==1 && zero->tf==1)
		return (one->val)^(zero->val);
	else if(one->zero==NULL)
		return get(one->one,zero->zero==NULL?zero->one:zero->zero);
	else if(one->one==NULL)
		return get(one->zero,zero->one==NULL?zero->zero:zero->one);
	else if(zero->zero==NULL)
		return get(one->zero,zero->one);
	else if(zero->one==NULL)
		return get(one->one,zero->zero);
	else
		return max(get(one->one,zero->zero),get(one->zero,zero->one));
}

int findMaximumXOR(int* arr,int n)
{
	createTrie(arr,n);
	struct Trie *pointer=root;
	while(pointer->one==NULL || pointer->zero==NULL)
	{
		pointer=pointer->zero!=NULL?pointer->zero:pointer->one;
	}
	return get(pointer->one,pointer->zero);
}
Comments (0)