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 2N 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, 2N] 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 edgesint 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 Codeint 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 approachimport java.util.*;Â
class GFG{Â
// Function to find the maximum Bitwise// AND of connected components possible// by connecting a graph using M edgesstatic 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 Codepublic 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 edgesdef 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 Codeif __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 approachusing System;Â
class GFG{     // Function to find the maximum Bitwise// AND of connected components possible// by connecting a graph using M edgesstatic 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 Codestatic 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 edgesfunction 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:Â
0
Â
Time Complexity: O((2N)*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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
