Dada una array cuadrada simétrica mat[][] de tamaño N , la tarea es encontrar la suma mínima posible de una array arr[] de tamaño N , tal que para i != j , el valor de Bitwise AND de arr[i ] y arr[j] es mat[i][j] .
Ejemplos:
Entrada: mat[][] = {{-1, 0, 1, 1, 1}, {0, -1, 2, 0, 2}, {1, 2, -1, 1, 3}, {1 , 0, 1, -1, -1}, {1, 2, 3, 1, -1}}
Salida: 10
Explicación:
la array que satisface los criterios anteriores es {1, 2, 3, 1, 3}.
La suma de los elementos de la array es 1 + 2 + 3 + 1 + 3 = 10, que es el mínimo.Entrada: mat[][] = {{-1, 2, 3}, {2, -1, 7}, {3, 7, -1}}
Salida: 17
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- La representación binaria de Bitwise AND de dos números tiene solo el conjunto de bits que se establece en ambos números.
- Entonces, a partir de la propiedad Bitwise AND , se puede observar que un número en la array resultante debe tener todos los bits establecidos en al menos uno de los elementos de la array en la i -ésima fila.
- Por lo tanto, el número en la i -ésima posición en la array resultante es Bitwise OR de todos los elementos de la array en la i -ésima fila.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos sum a 0 , que almacene la suma mínima posible de la array .
- Iterar sobre el rango [0, N – 1] y agregar el valor de Bitwise OR de todos los elementos de la array en la i -ésima fila excepto mat[i][i] a la variable sum .
- Después de completar los pasos anteriores, imprima el valor de la suma como la suma posible resultante .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum sum
// of the array such that Bitwise
// AND of arr[i] ana arr[j] is mat[i][j]
int findMinSum(vector<vector<int> > mat,
int N)
{
// Stores the minimum possible sum
int sum = 0;
// Traverse the range [0, N - 1]
for (int i = 0; i < N; i++) {
// Stores the Bitwise OR of
// all the element of a row
int res = 0;
// Traverse the range [0, N - 1]
for (int j = 0; j < N; j++) {
// If i not equal to j
if (i != j) {
// Update the value of
// res
res |= mat[i][j];
}
}
// Increment the sum by res
sum += res;
}
// Return minimum possible sum
return sum;
}
// Driver Code
int main()
{
vector<vector<int> > mat
= { { -1, 2, 3 }, { 9, -1, 7 }, { 4, 5, -1 } };
int N = mat.size();
cout << findMinSum(mat, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the minimum sum
// of the array such that Bitwise
// AND of arr[i] ana arr[j] is mat[i][j]
static int findMinSum(int mat[][], int N)
{
// Stores the minimum possible sum
int sum = 0;
// Traverse the range [0, N - 1]
for(int i = 0; i < N; i++)
{
// Stores the Bitwise OR of
// all the element of a row
int res = 0;
// Traverse the range [0, N - 1]
for(int j = 0; j < N; j++)
{
// If i not equal to j
if (i != j)
{
// Update the value of
// res
res |= mat[i][j];
}
}
// Increment the sum by res
sum += res;
}
// Return minimum possible sum
return sum;
}
// Driver Code
public static void main(String[] args)
{
int mat[][] = { { -1, 2, 3 },
{ 9, -1, 7 },
{ 4, 5, -1 } };
int N = mat.length;
System.out.println(findMinSum(mat, N));
}
}
// This code is contributed by Kingash
Python3
# Python 3 program of the above approach # Function to find the minimum sum # of the array such that Bitwise # AND of arr[i] ana arr[j] is mat[i][j] def findMinSum(mat, N): # Stores the minimum possible sum sum1 = 0 # Traverse the range [0, N - 1] for i in range(N): # Stores the Bitwise OR of # all the element of a row res = 0 # Traverse the range [0, N - 1] for j in range(N): # If i not equal to j if (i != j): # Update the value of # res res |= mat[i][j] # Increment the sum by res sum1 += res # Return minimum possible sum return sum1 # Driver code if __name__ == '__main__': mat = [[-1, 2, 3], [9, -1, 7], [4, 5,-1]] N = 3 print(findMinSum(mat, N)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum sum
// of the array such that Bitwise
// AND of arr[i] ana arr[j] is mat[i][j]
static int findMinSum(int[,] mat, int N)
{
// Stores the minimum possible sum
int sum = 0;
// Traverse the range [0, N - 1]
for(int i = 0; i < N; i++)
{
// Stores the Bitwise OR of
// all the element of a row
int res = 0;
// Traverse the range [0, N - 1]
for(int j = 0; j < N; j++)
{
// If i not equal to j
if (i != j)
{
// Update the value of
// res
res |= mat[i, j];
}
}
// Increment the sum by res
sum += res;
}
// Return minimum possible sum
return sum;
}
// Driver Code
public static void Main(string[] args)
{
int[,] mat = { { -1, 2, 3 },
{ 9, -1, 7 },
{ 4, 5, -1 } };
int N = mat.GetLength(0);
Console.WriteLine(findMinSum(mat, N));
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum sum
// of the array such that Bitwise
// AND of arr[i] ana arr[j] is mat[i][j]
function findMinSum(mat, N)
{
// Stores the minimum possible sum
var sum = 0;
// Traverse the range [0, N - 1]
for(var i = 0; i < N; i++)
{
// Stores the Bitwise OR of
// all the element of a row
var res = 0;
// Traverse the range [0, N - 1]
for(var j = 0; j < N; j++)
{
// If i not equal to j
if (i != j)
{
// Update the value of
// res
res |= mat[i][j];
}
}
// Increment the sum by res
sum += res;
}
// Return minimum possible sum
return sum;
}
// Driver Code
var mat = [ [ -1, 2, 3 ],
[ 9, -1, 7 ],
[ 4, 5, -1 ] ];
var N = mat.length;
document.write(findMinSum(mat, N));
// This code is contributed by Ankita saini
</script>
Producción:
23
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA