c - XOR maximization using a trie -
i trying solve question-
given array of unsigned 32-bit ints, choose 2 in-bounds indices i, j maximize value of a[i] ^ a[j], ^ bitwise xor (exclusive or) operator.
example input:
4 2 0 13 49
output:
60
- explanation: 13 ^ 49 60
here code
#include <stdio.h> void insert(int n, int pos, struct node *t); int find(struct node *p1, struct node *p2); struct node *alloc(); struct node{ int value; struct node *left; struct node *right; }; int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); struct node root; root.value = 0; root.left = root.right = null; while (n--) { int num; scanf("%d", &num); insert(num, 31 , &root); } int max = find(&root, &root); printf("%d\n", max); } return 0; } void insert(int n, int pos, struct node *t) { if (pos >= 0) { struct node *m; int bit = (1 << pos)&n; if (bit) { if (t->right == null) { m=alloc(); m->value = 1; m->left = null; m->right = null; t->right = m; } if (pos == 0) { m=alloc(); m->value = n; m->left = null; m->right = null; t->left = m; } insert(n, pos - 1, t->right); } else { if (t->left == null) { m = alloc(); m->value = 0; m->left = null; m->right = null; t->left = m; } if (pos == 0) { m=alloc(); m->value = n; m->left = null; m->right = null; t->left = m; } insert(n, pos - 1, t->left); } } } int find(struct node *p1, struct node *p2) { if ((p1->left != null) ||(p1->right != null)) { int n01 = 0; int n10 = 0; if (p1->left != null && p2->right != null) { n01 = find(p1->left, p2->right); } if ((p1->right != null) && (p2->left != null)) { n10 = find(p2->left, p1->right); } else { if (p1->left!=null && p2->left!=null) n01 = find(p1->left, p2->left); else n10 = find(p1->right, p2->right); } return (n01 > n10 ? n01 : n10); } else { return p1->value^p2->value; } } struct node *alloc() { return (struct node *) malloc(sizeof(struct node)); } i getting 0 output.i know there mistakes in code.please me in finding mistakes or if necessary right solution.
Comments
Post a Comment