Connect a graph by M edges such that the graph does not contain any cycle and Bitwise AND of connected vertices is maximum

0 0 7 minutes read

Given an array arr[] consisting of values of N vertices of an initially unconnected Graph and an integer M, the task is to connect some vertices of the graph with exactly M edges, forming only one connected component, such that no cycle can be formed and Bitwise AND of the connected vertices is maximum possible.

Examples:

Input: arr[] = {1, 2, 3, 4}, M = 2
Output: 0
Explanation:
Following arrangement of M edges between the given vertices are:
1->2->3 (1 & 2 & 3 = 0).
2->3->4 (2 & 3 & 4 = 0).
3->4->1 (3 & 4 & 1 = 0).
1->2->4 (1 & 2 & 4 = 0).
Therefore, the maximum Bitwise AND value among all the cases is 0.

Input: arr[] = {4, 5, 6}, M = 2
Output: 4
Explanation:
Only possible way to add M edges is 4 -> 5 -> 6 (4 & 5 & 6 = 4).
Therefore, the maximum Bitwise AND value possible is 4.

Approach: The idea to solve the given problem is to generate all possible combinations of connecting vertices using M edges and print the maximum Bitwise AND among all possible combinations.

The total number of ways for connecting N vertices is 2^N and there should be (M + 1) vertices to make only one connected component. Follow the steps to solve the given problem:

Initialize two variables, say AND and ans as 0 to store the maximum Bitwise AND, and Bitwise AND of nodes of any possible connected component respectively.
Iterate over the range [1, 2^N] using a variable, say i, and perform the following steps:
- If i has (M + 1) set bits, then find the Bitwise AND of the position of set bits and store it in the variable, say ans.
- If the value of AND exceeds ans, then update the value of AND as ans.
After completing the above steps, print the value of AND as the resultant maximum Bitwise AND.

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
// AND of connected components possible
// by connecting a graph using M edges
int maximumAND(int arr[], int n, int m)
{
    // Stores total number of
    // ways to connect the graph
    int tot = 1 << n;
 
    // Stores the maximum Bitwise AND
    int mx = 0;
 
    // Iterate over the range [0, 2^n]
    for (int bm = 0; bm < tot; bm++) {
        // Store the Bitwise AND of
        // the connected vertices
        int andans = 0;
 
        // Store the count of the
        // connected vertices
        int count = 0;
 
        // Check for all the bits
        for (int i = 0; i < n; ++i) {
            // If i-th bit is set
            if ((bm >> i) & 1) {
                // If the first vertex is added
                if (count == 0) {
                    // Set andans equal to arr[i]
                    andans = arr[i];
                }
                else {
                    // Calculate Bitwise AND
                    // of arr[i] with andans
                    andans = andans & arr[i];
                }
 
                // Increase the count of
                // connected vertices
                count++;
            }
        }
 
        // If number of connected vertices
        // is (m + 1), no cycle is formed
        if (count == (m + 1)) {
            // Find the maximum Bitwise
            // AND value possible
            mx = max(mx, andans);
        }
    }
 
    // Return the maximum
    // Bitwise AND possible
    return mx;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int M = 2;
 
    cout << maximumAND(arr, N, M);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the maximum Bitwise
// AND of connected components possible
// by connecting a graph using M edges
static int maximumAND(int arr[], int n, int m)
{
     
    // Stores total number of
    // ways to connect the graph
    int tot = 1 << n;
 
    // Stores the maximum Bitwise AND
    int mx = 0;
 
    // Iterate over the range [0, 2^n]
    for(int bm = 0; bm < tot; bm++) 
    {
         
        // Store the Bitwise AND of
        // the connected vertices
        int andans = 0;
 
        // Store the count of the
        // connected vertices
        int count = 0;
 
        // Check for all the bits
        for(int i = 0; i < n; ++i)
        {
             
            // If i-th bit is set
            if (((bm >> i) & 1) != 0) 
            {
                 
                // If the first vertex is added
                if (count == 0) 
                {
                     
                    // Set andans equal to arr[i]
                    andans = arr[i];
                }
                else
                {
                     
                    // Calculate Bitwise AND
                    // of arr[i] with andans
                    andans = andans & arr[i];
                }
 
                // Increase the count of
                // connected vertices
                count++;
            }
        }
 
        // If number of connected vertices
        // is (m + 1), no cycle is formed
        if (count == (m + 1)) 
        {
             
            // Find the maximum Bitwise
            // AND value possible
            mx = Math.max(mx, andans);
        }
    }
 
    // Return the maximum
    // Bitwise AND possible
    return mx;
}
 
// Driver Code
public static void main(String args[])
{
    int arr[] = { 1, 2, 3, 4 };
    int N = arr.length;
    int M = 2;
 
    System.out.println(maximumAND(arr, N, M));
}
}
 
// This code is contributed by souravghosh0416

Python3

# Python3 program for the above approach
 
# Function to find the maximum Bitwise
# AND of connected components possible
# by connecting a graph using M edges
def maximumAND(arr, n, m):
   
    # Stores total number of
    # ways to connect the graph
    tot = 1 << n
 
    # Stores the maximum Bitwise AND
    mx = 0
 
    # Iterate over the range [0, 2^n]
    for bm in range(tot):
       
        # Store the Bitwise AND of
        # the connected vertices
        andans = 0
 
        # Store the count of the
        # connected vertices
        count = 0
 
        # Check for all the bits
        for i in range(n):
           
            # If i-th bit is set
            if ((bm >> i) & 1):
               
                # If the first vertex is added
                if (count == 0):
                   
                    # Set andans equal to arr[i]
                    andans = arr[i]
                else:
                    # Calculate Bitwise AND
                    # of arr[i] with andans
                    andans = andans & arr[i]
 
                # Increase the count of
                # connected vertices
                count += 1
 
        # If number of connected vertices
        # is (m + 1), no cycle is formed
        if (count == (m + 1)):
           
            # Find the maximum Bitwise
            # AND value possible
            mx = max(mx, andans)
 
    # Return the maximum
    # Bitwise AND possible
    return mx
 
# Driver Code
if __name__ == '__main__':
    arr = [1, 2, 3, 4]
    N = len(arr)
    M = 2
 
    print (maximumAND(arr, N, M))
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the maximum Bitwise
// AND of connected components possible
// by connecting a graph using M edges
static int maximumAND(int[] arr, int n, int m)
{
     
    // Stores total number of
    // ways to connect the graph
    int tot = 1 << n;
  
    // Stores the maximum Bitwise AND
    int mx = 0;
  
    // Iterate over the range [0, 2^n]
    for(int bm = 0; bm < tot; bm++)
    {
         
        // Store the Bitwise AND of
        // the connected vertices
        int andans = 0;
  
        // Store the count of the
        // connected vertices
        int count = 0;
  
        // Check for all the bits
        for(int i = 0; i < n; ++i) 
        {
             
            // If i-th bit is set
            if (((bm >> i) & 1) != 0 )
            {
                 
                // If the first vertex is added
                if (count == 0) 
                {
                     
                    // Set andans equal to arr[i]
                    andans = arr[i];
                }
                else
                {
                     
                    // Calculate Bitwise AND
                    // of arr[i] with andans
                    andans = andans & arr[i];
                }
  
                // Increase the count of
                // connected vertices
                count++;
            }
        }
  
        // If number of connected vertices
        // is (m + 1), no cycle is formed
        if (count == (m + 1))
        {
             
            // Find the maximum Bitwise
            // AND value possible
            mx = Math.Max(mx, andans);
        }
    }
  
    // Return the maximum
    // Bitwise AND possible
    return mx;
}
  
// Driver Code
static public void Main ()
{
    int[] arr = { 1, 2, 3, 4 };
    int N = arr.Length;
    int M = 2;
     
    Console.WriteLine(maximumAND(arr, N, M));
}
}
 
// This code is contributed by avanitrachhadiya2155

Javascript

<script>
// JavaScript program for the above approach
 
// Function to find the maximum Bitwise
// AND of connected components possible
// by connecting a graph using M edges
function maximumAND(arr, n, m)
{
      
    // Stores total number of
    // ways to connect the graph
    let tot = 1 << n;
  
    // Stores the maximum Bitwise AND
    let mx = 0;
  
    // Iterate over the range [0, 2^n]
    for(let bm = 0; bm < tot; bm++)
    {
          
        // Store the Bitwise AND of
        // the connected vertices
        let andans = 0;
  
        // Store the count of the
        // connected vertices
        let count = 0;
  
        // Check for all the bits
        for(let i = 0; i < n; ++i)
        {
              
            // If i-th bit is set
            if (((bm >> i) & 1) != 0)
            {
                  
                // If the first vertex is added
                if (count == 0)
                {
                      
                    // Set andans equal to arr[i]
                    andans = arr[i];
                }
                else
                {
                      
                    // Calculate Bitwise AND
                    // of arr[i] with andans
                    andans = andans & arr[i];
                }
  
                // Increase the count of
                // connected vertices
                count++;
            }
        }
  
        // If number of connected vertices
        // is (m + 1), no cycle is formed
        if (count == (m + 1))
        {
              
            // Find the maximum Bitwise
            // AND value possible
            mx = Math.max(mx, andans);
        }
    }
  
    // Return the maximum
    // Bitwise AND possible
    return mx;
}
 
// Driver Code
 
    let arr = [ 1, 2, 3, 4 ];
    let N = arr.length;
    let M = 2;
  
    document.write(maximumAND(arr, N, M));
     
</script>

Output:

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!