Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Maximize Bitwise XOR of Ok with two numbers from Array

[ad_1]

Given an integer Ok and an array arr[] of measurement N, the duty is to decide on two components from the array in such a manner that the Bitwise XOR of these two with Ok (i.e. Ok ⊕ First chosen aspect ⊕ Second chosen aspect) is the utmost. 

Notice: Any array aspect will be chosen as many instances as attainable

Examples:

Enter: N = 3, Ok = 2, arr[]= [1, 2, 3]
Output: 3
Clarification: If we select one aspect from the second index 
and one other one from the third index, then the XOR of triplet 
shall be 2 ^ 2 ^ 3 = 3, which is the utmost attainable.

Enter: N = 3, Ok = 7, arr[] = [4, 2, 3]
Output: 7
Clarification: If we select each the aspect from the third index,  
then the XOR of triplet shall be 7 ^ 3 ^ 3 = 7, which is the utmost attainable.

Enter: N = 3, Ok = 3, arr[] = [1, 2, 3]
Output: 3
Clarification: If we select each the aspect from the third index,  
then the XOR of triplet shall be 3 ^ 3 ^ 3 = 3, which is the utmost attainable.

 

Naive Strategy: The method to the issue is to:

Iterate over all of the distinctive pairs within the array and discover the xor worth of the triplet and maintain monitor of the utmost.

Comply with the steps talked about beneath to implement the above thought:

  • Use two nested loops for producing all of the distinctive pairs.
  • Discover the xor of the every triplets arr[i] ⊕ arr[j] ⊕ Ok.
  • Discover the utmost of xor for every pair.
  • On the finish return the utmost xor worth obtained.

Beneath is the implementation of the above method:

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int maxXor(vector<int>& v, int ok)

{

    

    

    int n = v.measurement(), ans = 0;

  

    

    

    for (int i = 0; i < n; i++) {

        for (int j = i; j < n; j++) {

            ans = max(ans, v[i] ^ v[j] ^ ok);

        }

    }

    return ans;

}

  

int predominant()

{

    int N = 3, Ok = 2;

    vector<int> arr = { 1, 2, 3 };

  

    

    cout << maxXor(arr, Ok);

    return 0;

}

Time Complexity: O(N * N)
Auxiliary House: O(1)

Environment friendly Strategy: The issue will be effectively solved utilizing Trie information construction primarily based on the next thought:

  • To maximise the xor of the triplet iterate over all the weather contemplating them because the second aspect. and select the third aspect effectively in such a manner that the xor of triplet is most attainable.
  • Maximize the XOR by selecting the opposite components in such a manner that the resultant bit is 1 more often than not, and provides precedence to the MSB first then to the LSB as a result of the contribution of MSB is at all times higher than the LSB in closing decimal worth. 
  • For this, traverse from the MSB to LSB and if the bit is about then we’ll seek for 0 in order that the resultant bit is 1 and vice versa.
  • Use Trie information construction. As a result of with a purpose to maximize the xor worth, we have to do the prefix seek for the complement of that quantity, which will be performed effectively utilizing trie. 

Comply with the beneath steps to resolve this downside:

  • Firstly add all the weather to the trie.
  • Each bit in a quantity has 2 potentialities: 0 & 1, So, we’ve got 2 pointers in each Trie Node: 
    • little one[0] -> pointing to 0 bit & 
    • little one[1] -> pointing to 1 bit.
  • Now insert all the weather into the trie.
    • Use a bitset of measurement 32 (bitset<32> B) and go from probably the most vital bit (MSB) to the least vital bit (LSB).
    • Now begin on the root of the Trie and verify if little one[0] or little one[1] is current (not NULL), relying upon the present bit B[j] (j ranges from 0 to the whole quantity bit) of the quantity.
    • If it’s current, go to its little one, if not, create a brand new Node at that little one (0 bit or 1 bit) and transfer to its little one.
  • Now traverse the array and take into account every aspect because the second chosen aspect.
  • Until now the present XOR worth of the triplet is Ok ^ arr[i].
  • Now discover the third aspect utilizing trie such that its xor with present xor is most.
    • Begin on the root of the Trie and on the MSB of the quantity (initialize ans = 0 to retailer the reply).
    • If the present bit is set within the present xor, go to little one[0] to verify if it’s not NULL. 
      • If it’s not NULL, add 2i-1 to ans (as a result of this bit shall be set within the reply), else go to little one[1].
    • If it’s not set, go to little one[1] to see it’s not NULL. 
      • If it’s not NULL, we add 2i-1 to ans, else we go to little one[0].
  • Discover the utmost (say maxi) among the many most attainable xor at every index.
  • Return maxi as the reply.

Beneath is the implementation of the above method :

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

class TrieNode {

public:

    TrieNode* little one[2];

  

    TrieNode()

    {

        

        this->little one[0] = NULL;

        

        this->little one[1] = NULL;

    }

};

  

TrieNode* newNode;

  

void insert(int x)

{

    TrieNode* t = newNode;

  

    

    bitset<32> bs(x);

  

    

    

    for (int j = 30; j >= 0; j--) {

        if (!t->little one[bs[j]]) {

            t->little one[bs[j]]

                = new TrieNode();

        }

        t = t->little one[bs[j]];

    }

}

  

int findMaxXor(int ok)

{

    TrieNode* t = newNode;

    bitset<32> bs(ok);

  

    

    

    int ans = 0;

    for (int j = 30; j >= 0; j--) {

  

        

        

        

        if (t->little one[!bs[j]]) {

            ans += (1 << j), t = t->little one[!bs[j]];

        }

        else {

            t = t->little one[bs[j]];

        }

    }

    return ans;

}

  

int maxXor(vector<int>& v, int Ok)

{

    int n = v.measurement();

  

    newNode = new TrieNode();

  

    

    for (int i = 0; i < n; i++) {

        insert(v[i]);

    }

  

    

    

    int ans = 0;

  

    

    

    for (int i = 0; i < n; i++) {

        ans = max(ans, findMaxXor(v[i] ^ Ok));

    }

  

    return ans;

}

  

int predominant()

{

    int N = 3, Ok = 2;

    vector<int> arr = { 1, 2, 3 };

  

    

    cout << maxXor(arr, Ok);

    return 0;

}

Time Complexity: O(N * logM) the place M is the utmost aspect of the array.
Auxiliary House: O(logM)

[ad_2]

Leave a Reply