## Introduction

In this blog, we will discuss an array problem that has been asked frequently in Interviews.

The problem is to find the Maximum Bitwise XOR of values of nodes of an Acyclic Graph made up of N given vertices using M edges.

Let’s look at the problem.

### Problem Statement

We are given N number of vertices and M number of edges. First, we need to make all possible acyclic graphs with M edges and for all such possible graphs, find each of those xor values. We are asked to return the maximum of all xor values obtained.

### Sample example

**Example:**

```
Say, N given is 4 and M given is 2.
arr[]={1,2,3,4}
As there are 2 edges, then there will be 3 vertices.
All possible vertices and their xor values will be:
{1,2,3}, xor=0
{1,2,4}, xor=7
{2,3,4}, xor=5
{1,3,4}, xor=6
Maximum xor value obtained=7.
```

## Approach

Now the approach to find the Maximum Bitwise XOR of values of nodes of an Acyclic Graph made up of N given vertices using M edges.

First, calculate the number of vertices from the number of edges given.

Number of vertices=Number of edges+1.

⬇

Find all possible subsets of the given array.

⬇

Count the number of set bits.

⬇

We will include that element in the current xor for each possible set bit. We need to calculate xor of all possible subsets generated in this way.

⬇

Find the maximum of all obtained xor and return it.

This approach requires no extra space, so space complexity becomes O(1). the time taken will be the time to generate subarrays possible, i.e. O(2^n), and then for each subarray, we calculate xor values. Therefore, the time complexity becomes O(n*(2^n)).

Till now, I guess you must have got the basic conceptual idea of what has been asked in the given problem statement. So, I recommend you first give it a try.

__https://www.codingninjas.com/studio__

### PseudoCode

**Algorithm**

To find the Maximum Bitwise XOR of values of nodes of an Acyclic Graph made up of N given vertices using M edges.:

___________________________________________________________________

**procedure** maximumXOR(int arr[], int n, int K):

___________________________________________________________________

**1.** K++

**2**. maxXor = INT_MIN

**3.** for (i = 0 to i < (1 << n)):

if (__builtin_popcount(i) == K):

cur_xor = 0

for (j = 0 to j < n):

if (i & (1 << j)): cur_xor = cur_xor ^ arr[j]

maxXor = max(maxXor, cur_xor)

**4.** Return maxXor

**5. end procedure**

___________________________________________________________________