What is an acyclic graph?

A graph with no cycles is termed as an acyclic graph. There will be no stop nodes in such a graph.

What do you mean by bitwise xor?

This is a binary operation. It calculates the “exclusive or” of the number. If only one bit is true, the answer will be true, but if both values are true or if both values are false, the answer will be false.

What is __builtin_popcount()?

This is a built-in function in c++. It counts the number of true values or set bits in an integer.

Table of contents

Introduction

1.1.

Problem Statement

1.2.

Sample example

Approach

2.1.

PseudoCode

Implementation in C++

3.1.

Complexity Analysis

FAQs

Key Takeaways

Last Updated: Mar 27, 2024

Maximum Bitwise XOR of values of nodes of an Acyclic Graph made up of N given vertices using M edges

Author Urwashi Priya

Do you think IIT Guwahati certified course can help you in your career?

Yes

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
___________________________________________________________________

Implementation in C++

// C++ program to find the Maximum Bitwise XOR of values of nodes of an Acyclic Graph made up of N given vertices using M edges.
#include <bits/stdc++.h>
using namespace std;

int maximumXOR(int arr[], int n, int K)
{
    //number of vertices will be one greater than the number of edges
	K++;

	// a variable to store the maximum Bitwise XOR
	int maxXor = INT_MIN;

	// to Generate all possible subsets of the given array
	for (int i = 0; i < (1 << n); i++) {

		// counting the number of set bits 
		if (__builtin_popcount(i) == K) {

			int cur_xor = 0;

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

				// If jth bit is set in i then we will include jth element in the current xor
				if (i & (1 << j))
					cur_xor = cur_xor ^ arr[j];
			}

			// Updating the maximum Bitwise XOR
			maxXor = max(maxXor, cur_xor);
		}
	}

	return maxXor;
}

int main()
{
    int N,M;
    int arr[N];
    cin>>N>>M;
    for(int i=0; i<N; i++){
        cin>>arr[i];
    }
	cout << maximumXOR(arr, N, M);

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Sample Input: 
4 2
1 2 3 4

Sample Output:
7

Complexity Analysis

Time Complexity: O(N*(2^N)).

Analysing Time Complexity:
This is the time complexity to generate all possible subarrays.

Space complexity: O(1), as no extra space is required.

FAQs

What is an acyclic graph?
A graph with no cycles is termed as an acyclic graph. There will be no stop nodes in such a graph.
What do you mean by bitwise xor?
This is a binary operation. It calculates the “exclusive or” of the number. If only one bit is true, the answer will be true, but if both values are true or if both values are false, the answer will be false.
What is __builtin_popcount()?
This is a built-in function in c++. It counts the number of true values or set bits in an integer.

Key Takeaways

This article taught us to find the Maximum Bitwise XOR of values of nodes of an Acyclic Graph made up of N given vertices using M edges. We discussed its implementation using illustrations, pseudocode and then optimised proper code.

We hope you could take away all critical techniques like analysing problems by walking over the execution of the examples and finding out the recursive pattern followed in most problems.

Now, we recommend you practice problem sets based on arrays to master your fundamentals. You can get a wide range of questions similar to this problem on Coding Ninjas Studio.
It's not the end. Must solve the problem of similar types.

Happy Coding.