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

Given N nodes valued by [1, N], an array arr[] consisting of N positive integers such that the ith node ( 1-based indexing ) has the value arr[i] and an integer M, the task is to find the maximum Bitwise XOR of node values of an acyclic graph formed by M edges.

Examples:

Input: arr[]= {1, 2, 3, 4}, M = 2
Output: 7
Explanation:
Acyclic graphs having M(= 2) edges can be formed by vertices as:

  1. {1, 2, 3}: The value of the Bitwise XOR of vertices is 1^2^3 = 0.
  2. {2, 3, 4}: The value of the Bitwise XOR of vertices is 2^3^4 = 5.
  3. {1, 2, 4}: The value of the Bitwise XOR of vertices is 1^2^4 = 7.
  4. {1, 4, 3}: The value of the Bitwise XOR of vertices is 1^4^3 = 6.

Therefore, the maximum Bitwise XOR among all possible acyclic graphs is 7. 

Input: arr[] = {2, 4, 8, 16}, M = 2
Output: 28

Approach: The given problem can be solved by using the fact that an acyclic graph having M edges must have (M + 1) vertices. Therefore, the task is reduced to finding the maximum Bitwise XOR of a subset of the array arr[] having (M + 1) vertices. Follow the steps below to solve the problem:

  • Initialize a variable, say maxAns as 0 that stores the maximum Bitwise XOR of an acyclic graph having M edges.
  • Generate all possible subsets of the array arr[] and for each subset find the Bitwise XOR of the elements of the subset and update the value of maxAns to the maximum of maxAns and Bitwise XOR.
  • After completing the above steps, print the value of maxAns as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum Bitwise
// XOR of any subset of the array of size K
int maximumXOR(int arr[], int n, int K)
{
    // Number of node must K + 1 for
    // K edges
    K++;
 
    // Stores the maximum Bitwise XOR
    int maxXor = INT_MIN;
 
    // Generate all subsets of the array
    for (int i = 0; i < (1 << n); i++) {
 
        // __builtin_popcount() returns
        // the number of sets bits in
        // an integer
        if (__builtin_popcount(i) == K) {
 
            // Initialize current xor as 0
            int cur_xor = 0;
 
            for (int j = 0; j < n; j++) {
 
                // If jth bit is set in i
                // then include jth element
                // in the current xor
                if (i & (1 << j))
                    cur_xor = cur_xor ^ arr[j];
            }
 
            // Update the maximum Bitwise
            // XOR obtained so far
            maxXor = max(maxXor, cur_xor);
        }
    }
 
    // Return the maximum XOR
    return maxXor;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int N = sizeof(arr) / sizeof(int);
    int M = 2;
    cout << maximumXOR(arr, N, M);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to find the maximum Bitwise
// XOR of any subset of the array of size K
static int maximumXOR(int arr[], int n, int K)
{
     
    // Number of node must K + 1 for
    // K edges
    K++;
 
    // Stores the maximum Bitwise XOR
    int maxXor = Integer.MIN_VALUE;
 
    // Generate all subsets of the array
    for(int i = 0; i < (1 << n); i++)
    {
         
        // Integer.bitCount() returns
        // the number of sets bits in
        // an integer
        if (Integer.bitCount(i) == K)
        {
             
            // Initialize current xor as 0
            int cur_xor = 0;
 
            for(int j = 0; j < n; j++)
            {
                 
                // If jth bit is set in i
                // then include jth element
                // in the current xor
                if ((i & (1 << j)) != 0)
                    cur_xor = cur_xor ^ arr[j];
            }
 
            // Update the maximum Bitwise
            // XOR obtained so far
            maxXor = Math.max(maxXor, cur_xor);
        }
    }
 
    // Return the maximum XOR
    return maxXor;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 4 };
    int N = arr.length;
    int M = 2;
     
    System.out.println(maximumXOR(arr, N, M));
}
}
 
// This code is contributed by Kingash

Python3

# Python3 program for the above approach
 
# Function to find the maximum Bitwise
# XOR of any subset of the array of size K
def maximumXOR(arr, n, K):
   
    # Number of node must K + 1 for
    # K edges
    K += 1
 
    # Stores the maximum Bitwise XOR
    maxXor = -10**9
 
    # Generate all subsets of the array
    for i in range(1<<n):
       
        # __builtin_popcount() returns
        # the number of sets bits in
        # an integer
        if (bin(i).count('1') == K):
 
            # Initialize current xor as 0
            cur_xor = 0
 
            for j in range(n):
               
                # If jth bit is set in i
                # then include jth element
                # in the current xor
                if (i & (1 << j)):
                    cur_xor = cur_xor ^ arr[j]
 
            # Update the maximum Bitwise
            # XOR obtained so far
            maxXor = max(maxXor, cur_xor)
 
    # Return the maximum XOR
    return maxXor
 
# Driver Code
if __name__ == '__main__':
    arr= [1, 2, 3, 4 ]
    N = len(arr)
    M = 2
    print (maximumXOR(arr, N, M))
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
using System.Linq;
 
class GFG{
 
// Function to find the maximum Bitwise
// XOR of any subset of the array of size K
static int maximumXOR(int []arr, int n, int K)
{
     
    // Number of node must K + 1 for
    // K edges
    K++;
 
    // Stores the maximum Bitwise XOR
    int maxXor = Int32.MinValue;
 
    // Generate all subsets of the array
    for(int i = 0; i < (1 << n); i++)
    {
         
        // Finding number of sets
        // bits in an integer
        if (Convert.ToString(i, 2).Count(c => c == '1') == K)
        {
             
            // Initialize current xor as 0
            int cur_xor = 0;
 
            for(int j = 0; j < n; j++)
            {
                 
                // If jth bit is set in i
                // then include jth element
                // in the current xor
                if ((i & (1 << j)) != 0)
                    cur_xor = cur_xor ^ arr[j];
            }
 
            // Update the maximum Bitwise
            // XOR obtained so far
            maxXor = Math.Max(maxXor, cur_xor);
        }
    }
 
    // Return the maximum XOR
    return maxXor;
}
 
// Driver code
static void Main()
{
    int [] arr = { 1, 2, 3, 4 };
    int N = arr.Length;
    int M = 2;
     
    Console.WriteLine(maximumXOR(arr, N, M));
}
}
 
// This code is contributed by jana_sayantan.

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the maximum Bitwise
// XOR of any subset of the array of size K
function maximumXOR(arr, n, K) {
    // Number of node must K + 1 for
    // K edges
    K++;
 
    // Stores the maximum Bitwise XOR
    let maxXor = Number.MIN_SAFE_INTEGER;
 
    // Generate all subsets of the array
    for (let i = 0; i < (1 << n); i++) {
 
        // __builtin_popcount() returns
        // the number of sets bits in
        // an integer
        if ((i).toString(2).split('').
            filter(x => x == '1').length == K) {
 
            // Initialize current xor as 0
            let cur_xor = 0;
 
            for (let j = 0; j < n; j++) {
 
                // If jth bit is set in i
                // then include jth element
                // in the current xor
                if (i & (1 << j))
                    cur_xor = cur_xor ^ arr[j];
            }
 
            // Update the maximum Bitwise
            // XOR obtained so far
            maxXor = Math.max(maxXor, cur_xor);
        }
    }
 
    // Return the maximum XOR
    return maxXor;
}
 
// Driver Code
 
let arr = [1, 2, 3, 4];
let N = arr.length;
let M = 2;
document.write(maximumXOR(arr, N, M));
 
 
// This code is contributed by _saurabh_jaiswal
</script>

Output: 

7

 

Time Complexity: O(N * 2N) 
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Graph

Related
Maximum cost path from source node to destination node via at most K intermediate nodes Maximum cost path from source node to destination node via at most K intermediate nodes
Java Program to Implement of Gabow Scaling Algorithm Java Program to Implement of Gabow Scaling Algorithm
Path from a given source to a given destination having Kth largest weight in a Graph Path from a given source to a given destination having Kth largest weight in a Graph
Connect a graph by M edges such that the graph does not contain any cycle and Bitwise AND of connected vertices is maximum Connect a graph by M edges such that the graph does not contain any cycle and Bitwise AND of connected vertices is maximum
Equivalent Serial Schedule of Conflict Serializable Schedule in DBMS Equivalent Serial Schedule of Conflict Serializable Schedule in DBMS

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje