HackerRankSolutions/Solutions/MaximumXor.cs at master · hamidmayeli/HackerRankSolutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// Maximum Xor
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Solution {

    class Trie
    {
        Trie left;
        Trie right;

        public void Insert(Trie head, int n)
        {
            for (int i = 31; i >= 0; i--)
            {
                int value = (n >> i) & 1;
                if (value == 0)
                {//move left
                    if (head.left == null)
                        head.left = new Trie();
                    head = head.left;
                }
                else
                {//move right
                    if (head.right == null)
                        head.right = new Trie();
                    head = head.right;
                }
            }
        }

        public uint MaxXor(Trie head, int n)
        {
            uint max = 0;
            for (int i = 31; i >= 0; i--)
            {
                int value = (n >> i) & 1;
                //for max xor you have to move alternate
                if (value == 0)
                {//move right
                    if (head.right != null)
                    {
                        max += (uint)Math.Pow(2, i);
                        head = head.right;
                    }
                    else
                        head = head.left;
                }
                else
                {//move left
                    if (head.left != null)
                    {
                        max += (uint)Math.Pow(2, i);
                        head = head.left;
                    }
                    else
                        head = head.right;
                }
            }
            return max;
        }
    }
    static int[] maxXor(int[] arr, int[] queries)
    {
        int[] result = new int[queries.Length];
        Trie head = new Trie();
        for (int i = 0; i < arr.Length; i++)
        {
            head.Insert(head, arr[i]);
        }
        for (int i = 0; i < queries.Length; i++)
        {
            result[i] = Convert.ToInt32(head.MaxXor(head, queries[i]));
        }
        return result;
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int n = Convert.ToInt32(Console.ReadLine());

        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), arrTemp => Convert.ToInt32(arrTemp))
        ;
        int m = Convert.ToInt32(Console.ReadLine());

        int[] queries = new int [m];

        for (int i = 0; i < m; i++) {
            int queriesItem = Convert.ToInt32(Console.ReadLine());
            queries[i] = queriesItem;
        }

        int[] result = maxXor(arr, queries);

        textWriter.WriteLine(string.Join("\n", result));

        textWriter.Flush();
        textWriter.Close();
    }
}