Dada una array arr[] que consta de valores de N vértices de un gráfico inicialmente no conectado y un número entero M , la tarea es conectar algunos vértices del gráfico con exactamente M bordes, formando solo un componente conectado , de modo que no se pueda formar ningún ciclo . y Bitwise AND de los vértices conectados es el máximo posible.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}, M = 2
Salida: 0
Explicación:
La siguiente disposición de M aristas entre los vértices dados es:
1->2->3 (1 & 2 & 3 = 0 ).
2->3->4 (2 y 3 y 4 = 0).
3->4->1 (3 y 4 y 1 = 0).
1->2->4 (1 y 2 y 4 = 0).
Por lo tanto, el valor AND bit a bit máximo entre todos los casos es 0.Entrada: arr[] = {4, 5, 6}, M = 2
Salida: 4
Explicación:
La única forma posible de agregar bordes M es 4 -> 5 -> 6 (4 & 5 & 6 = 4).
Por lo tanto, el valor AND bit a bit máximo posible es 4.
Enfoque: La idea para resolver el problema dado es generar todas las combinaciones posibles de vértices de conexión usando aristas M e imprimir el AND bit a bit máximo entre todas las combinaciones posibles.
El número total de formas para conectar N vértices es 2 N y debe haber (M + 1) vértices para hacer solo un componente conectado . Siga los pasos para resolver el problema dado:
- Inicialice dos variables, digamos AND y ans como 0 para almacenar el máximo AND bit a bit y AND bit a bit de Nodes de cualquier posible componente conectado respectivamente.
- Itere sobre el rango [1, 2 N ] usando una variable, digamos i , y realice los siguientes pasos:
- Si tengo (M + 1) bits establecidos , busque el AND bit a bit de la posición de los bits establecidos y guárdelo en la variable, digamos ans .
- Si el valor de AND excede ans, actualice el valor de AND como ans .
- Después de completar los pasos anteriores, imprima el valor de AND como el AND bit a bit máximo resultante .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
0
Complejidad temporal: O((2 N )*N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por tmprofessor y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA