Dada una array , mat[][] de tamaño N * M , la tarea es encontrar el número mínimo de operaciones requeridas para hacer que todos los elementos de al menos una fila de la array dada sean primos. En cada operación, combine dos filas cualquiera de la array en función de las siguientes condiciones:
- Si el k -ésimo elemento de ambas filas de la array, es decir, mat[i][k] y mat[j][k] son números primos o números compuestos, entonces el k -ésimo elemento de la fila fusionada contiene min(mat[i][ k], mat[j][k]) .
- De lo contrario, el k -ésimo elemento de la fila fusionada contiene el elemento que es primo.
Si no es posible obtener todos los elementos de una fila como números primos , imprima -1 .
Ejemplos:
Entrada: mat[][] = { { 4, 6, 5 }, { 2, 9, 12 }, { 32, 7, 18 }, { 12, 4, 35 } }
Salida: 2
Explicación:
Combinar mat[0 ] y mat[1] modifica mat[][] a { { 2, 6, 5 }, { 32, 7, 18 }, { 12, 4, 35 } }
Combinar mat[0] y mat[1] modifica mat [][] a { { 2, 7, 5 }, { 12, 4, 35 } }
Dado que la primera fila de la array consta solo de números primos, el resultado requerido es 2.Entrada: mat[][] = { {4, 6}, {8, 3} }
Salida: -1
Explicación:
La fusión de mat[0] y mat[1] modifica mat[][] a { { 4, 3 } }
Dado que ninguno de los elementos de la fila es primo, el resultado requerido es -1.
Planteamiento: El problema se puede resolver usando programación Dinámica con Bitmasks . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos máscara de bits , donde el i -ésimo bit de la máscara de bits almacena si la i -ésima columna de una fila es un número primo o no.
- Inicialice una array , digamos dp[] , donde dp[X] almacena el recuento mínimo de operaciones requeridas para obtener X recuento de números primos en una fila.
- Recorra cada fila de la array y actualice el valor de la máscara de bits para cada fila. Iterar sobre el rango [(1 << (M – 1)), 0] usando la variable j y actualizar el valor de dp[j | máscara de bits] a min(dp[j | máscara de bits], dp[j] + 1) .
- Finalmente, verifique si el número mínimo de operaciones requeridas para obtener M números primos seguidos es mayor que N o no, es decir, verifique si dp[(1 << (M – 1))] es mayor que N o no. Si se encuentra que es cierto, imprima -1 .
- De lo contrario, imprima el valor de (dp[(1 << (M – 1))] – 1) .
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;
const int N = 100001;
// Function to generate all prime
// numbers using Sieve of Eratosthenes
bool prime[N];
// Function to check if a number
// is prime or not
void sieve(int n)
{
// Initialize prime[]
// array to true
for(int i = 0 ; i <= n ; i++){
prime[i] = true;
}
// Iterate over the range
// [2, sqrt(n)]
for (int p = 2; p * p <= n; p++) {
// If p is a prime number
if (prime[p] == true) {
// Mark all multiples
// of i to false
for (int i = p * p; i <= n; i += p)
// Update i
prime[i] = false;
}
}
}
// Function to count prime
// numbers in a row
int BitMask(int a[],int n)
{
// i-th bit of bitmask check if
// i-th column is a prime or not
int bitmask = 0;
// Traverse the array
for (int i = 0; i < n ; i++) {
// if a[i] is a prime number
if (prime[a[i]]) {
// Update bitmask
bitmask |= (1 << i);
}
}
return bitmask;
}
// Function to find minimum operations
// to make all elements of at least one
// row of the matrix as prime numbers
int MinWays(int a[][4], int n, int m)
{
// dp[i]: Stores minimum operations
// to get i prime numbers in a row
int dp[1 << m];
// Initialize dp[] array
// to (n + 1)
for(int i = 0 ; i < (1 << m) ; i++){
dp[i] = n + 1;
}
// Traverse the array
for (int i = 0 ; i < n ; i++) {
// Stores count of prime
// numbers in a i-th row
int bitmask = BitMask(a[i], n);
// Iterate over the range
// [(1 << m) - 1, 0]
for (int j = (1 << m) - 1 ; j >= 0; j--) {
// If a row exist which
// contains j prime numbers
if (dp[j] != n + 1) {
// Update dp[j | bitmask]
dp[j | bitmask] = min(dp[j | bitmask], dp[j] + 1);
}
}
// Update dp[bitmask]
dp[bitmask] = 1;
}
// Return minimum operations to get a row
// of the matrix with all prime numbers
return (dp[(1 << m) - 1] - 1) == (n + 1) ? -1 : (dp[(1 << m) - 1] - 1);
}
// Driver code
int main()
{
// Stores length
int n = 4;
int mat[4][4] = { { 4, 6, 5, 8 },
{ 2, 9, 12, 14 },
{ 32, 7, 18, 16 },
{ 12, 4, 35, 17 } };
// Stores count of columns
// in the matrix
int m = sizeof(mat[0])/sizeof(mat[0][0]);
// Calculate all prime numbers in
// range [1, max] using sieve
int max = 10000;
sieve(max);
// Function Call
cout << MinWays(mat, n, m) << endl;
}
// This code is contributed by subhamgoyal2014.
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to generate all prime
// numbers using Sieve of Eratosthenes
private static boolean[] prime;
// Function to check if a number
// is prime or not
private static void sieve(int n)
{
// prime[i]: Check if i is a
// prime number or not
prime = new boolean[n + 1];
// Initialize prime[]
// array to true
Arrays.fill(prime, true);
// Iterate over the range
// [2, sqrt(n)]
for (int p = 2; p * p <= n;
p++) {
// If p is a prime number
if (prime[p] == true) {
// Mark all multiples
// of i to false
for (int i = p * p;
i <= n; i += p)
// Update i
prime[i] = false;
}
}
}
// Function to find minimum operations
// to make all elements of at least one
// row of the matrix as prime numbers
private static int MinWays(int[][] a,
int n, int m)
{
// dp[i]: Stores minimum operations
// to get i prime numbers in a row
int[] dp = new int[1 << m];
// Initialize dp[] array
// to (n + 1)
Arrays.fill(dp, n + 1);
// Traverse the array
for (int i = 0; i < a.length;
i++) {
// Stores count of prime
// numbers in a i-th row
int bitmask = BitMask(a[i]);
// Iterate over the range
// [(1 << m) - 1, 0]
for (int j = (1 << m) - 1;
j >= 0; j--) {
// If a row exist which
// contains j prime numbers
if (dp[j] != n + 1) {
// Update dp[j | bitmask]
dp[j | bitmask]
= Math.min(dp[j | bitmask],
dp[j] + 1);
}
}
// Update dp[bitmask]
dp[bitmask] = 1;
}
// Return minimum operations to get a row
// of the matrix with all prime numbers
return (dp[(1 << m) - 1] - 1) == (n + 1)
? -1
: (dp[(1 << m) - 1] - 1);
}
// Function to count prime
// numbers in a row
private static int BitMask(int[] a)
{
// i-th bit of bitmask check if
// i-th column is a prime or not
int bitmask = 0;
// Traverse the array
for (int i = 0; i < a.length;
i++) {
// if a[i] is a prime number
if (prime[a[i]]) {
// Update bitmask
bitmask |= (1 << i);
}
}
return bitmask;
}
// Driver Code
public static void main(String[] args)
{
int[][] mat = { { 4, 6, 5, 8 },
{ 2, 9, 12, 14 },
{ 32, 7, 18, 16 },
{ 12, 4, 35, 17 } };
// Stores count of columns
// in the matrix
int m = mat[0].length;
// Stores length
int n = mat.length;
// Calculate all prime numbers in
// range [1, max] using sieve
int max = 10000;
sieve(max);
// Function Call
System.out.println(
MinWays(mat, n, m));
}
}
Python3
# Python 3 program to implement # the above approach from math import sqrt # Function to generate all prime # numbers using Sieve of Eratosthenes prime = [True for i in range(10001)] # Function to check if a number # is prime or not def sieve(n): # prime[i]: Check if i is a # prime number or not global prime # Iterate over the range # [2, sqrt(n)] for p in range(2,int(sqrt(10000)) + 1, 1): # If p is a prime number if (prime[p] == True): # Mark all multiples # of i to false for i in range(p * p, 10001, p): # Update i prime[i] = False # Function to find minimum operations # to make all elements of at least one # row of the matrix as prime numbers def MinWays(a, n, m): # dp[i]: Stores minimum operations # to get i prime numbers in a row dp = [n + 1 for i in range(1 << m)] # Traverse the array for i in range(len(a)): # Stores count of prime # numbers in a i-th row bitmask = BitMask(a[i]) print(a[i], bitmask) # Iterate over the range # [(1 << m) - 1, 0] j = (1 << m) - 1 while(j >= 0): # If a row exist which # contains j prime numbers if (dp[j] != n + 1): # Update dp[j | bitmask] dp[j | bitmask] = min(dp[j | bitmask],dp[j] + 1) j -= 1 # Update dp[bitmask] dp[bitmask] = 1 # Return minimum operations to get a row # of the matrix with all prime numbers if (dp[(1 << m) - 1] - 1) == (n + 1): return -1 else: return (dp[(1 << m) - 1] - 1) # Function to count prime # numbers in a row def BitMask(a): global prime # i-th bit of bitmask check if # i-th column is a prime or not bitmask = 0 # Traverse the array for i in range(len(a)): # if a[i] is a prime number if (prime[a[i]]): # Update bitmask bitmask |= (1 << i) return bitmask # Driver Code if __name__ == '__main__': mat = [[4, 6, 5, 8], [2, 9, 12, 14], [32, 7, 18, 16], [12, 4, 35, 17]] # Stores count of columns # in the matrix m = len(mat[0]) # Stores length n = len(mat) # Calculate all prime numbers in # range [1, max] using sieve max = 10000 sieve(max) # Function Call print(MinWays(mat, n, m)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program to implement
// the above approach
using System;
public class GFG
{
// Function to generate all prime
// numbers using Sieve of Eratosthenes
private static bool[] prime;
// Function to check if a number
// is prime or not
private static void sieve(int n)
{
// prime[i]: Check if i is a
// prime number or not
prime = new bool[n + 1];
// Initialize prime[]
// array to true
for (int i = 0; i < prime.Length; i++)
prime[i] = true;
// Iterate over the range
// [2, sqrt(n)]
for (int p = 2; p * p <= n;
p++) {
// If p is a prime number
if (prime[p] == true)
{
// Mark all multiples
// of i to false
for (int i = p * p;
i <= n; i += p)
// Update i
prime[i] = false;
}
}
}
// Function to find minimum operations
// to make all elements of at least one
// row of the matrix as prime numbers
private static int MinWays(int[,] a,
int n, int m)
{
// dp[i]: Stores minimum operations
// to get i prime numbers in a row
int[] dp = new int[1 << m];
// Initialize []dp array
// to (n + 1)
for (int i = 0; i < dp.Length;i++)
{
dp[i] = n + 1;
}
// Traverse the array
for (int i = 0; i < a.GetLength(0);
i++)
{
// Stores count of prime
// numbers in a i-th row
int bitmask = BitMask(GetRow(a,i));
// Iterate over the range
// [(1 << m) - 1, 0]
for (int j = (1 << m) - 1;
j >= 0; j--)
{
// If a row exist which
// contains j prime numbers
if (dp[j] != n + 1)
{
// Update dp[j | bitmask]
dp[j | bitmask]
= Math.Min(dp[j | bitmask],
dp[j] + 1);
}
}
// Update dp[bitmask]
dp[bitmask] = 1;
}
// Return minimum operations to get a row
// of the matrix with all prime numbers
return (dp[(1 << m) - 1] - 1) == (n + 1)
? -1
: (dp[(1 << m) - 1] - 1);
}
// Function to count prime
// numbers in a row
private static int BitMask(int[] a)
{
// i-th bit of bitmask check if
// i-th column is a prime or not
int bitmask = 0;
// Traverse the array
for (int i = 0; i < a.Length;
i++) {
// if a[i] is a prime number
if (prime[a[i]])
{
// Update bitmask
bitmask |= (1 << i);
}
}
return bitmask;
}
public static int[] GetRow(int[,] matrix, int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new int[rowLength];
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver Code
public static void Main(String[] args)
{
int[,] mat = { { 4, 6, 5, 8 },
{ 2, 9, 12, 14 },
{ 32, 7, 18, 16 },
{ 12, 4, 35, 17 } };
// Stores count of columns
// in the matrix
int m = mat.GetLength(0);
// Stores length
int n = mat.GetLength(1);
// Calculate all prime numbers in
// range [1, max] using sieve
int max = 10000;
sieve(max);
// Function Call
Console.WriteLine(
MinWays(mat, n, m));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Function to generate all prime
// numbers using Sieve of Eratosthenes
let prime = [];
// Function to check if a number
// is prime or not
function sieve(n)
{
// prime[i]: Check if i is a
// prime number or not
prime = new Array(n + 1);
// Initialize prime[]
// array to true
for (let i = 0; i < prime.length; i++)
prime[i] = true;
// Iterate over the range
// [2, sqrt(n)]
for (let p = 2; p * p <= n;
p++) {
// If p is a prime number
if (prime[p] == true) {
// Mark all multiples
// of i to false
for (let i = p * p;
i <= n; i += p)
// Update i
prime[i] = false;
}
}
}
// Function to find minimum operations
// to make all elements of at least one
// row of the matrix as prime numbers
function MinWays(a, n, m)
{
// dp[i]: Stores minimum operations
// to get i prime numbers in a row
let dp = new Array(1 << m);
// Initialize dp[] array
// to (n + 1)
for (let i = 0; i < dp.length;i++)
{
dp[i] = n + 1;
}
// Traverse the array
for (let i = 0; i < a.length;
i++) {
// Stores count of prime
// numbers in a i-th row
let bitmask = BitMask(a[i]);
// Iterate over the range
// [(1 << m) - 1, 0]
for (let j = (1 << m) - 1;
j >= 0; j--) {
// If a row exist which
// contains j prime numbers
if (dp[j] != n + 1) {
// Update dp[j | bitmask]
dp[j | bitmask]
= Math.min(dp[j | bitmask],
dp[j] + 1);
}
}
// Update dp[bitmask]
dp[bitmask] = 1;
}
// Return minimum operations to get a row
// of the matrix with all prime numbers
return (dp[(1 << m) - 1] - 1) == (n + 1)
? -1
: (dp[(1 << m) - 1] - 1);
}
// Function to count prime
// numbers in a row
function BitMask(a)
{
// i-th bit of bitmask check if
// i-th column is a prime or not
let bitmask = 0;
// Traverse the array
for (let i = 0; i < a.length;
i++) {
// if a[i] is a prime number
if (prime[a[i]]) {
// Update bitmask
bitmask |= (1 << i);
}
}
return bitmask;
}
// Driver Code
let mat = [[ 4, 6, 5, 8 ],
[ 2, 9, 12, 14 ],
[ 32, 7, 18, 16 ],
[ 12, 4, 35, 17 ]];
// Stores count of columns
// in the matrix
let m = mat[0].length;
// Stores length
let n = mat.length;
// Calculate all prime numbers in
// range [1, max] using sieve
let max = 10000;
sieve(max);
// Function Call
document.write(
MinWays(mat, n, m));
</script>
Producción:
3
Complejidad de tiempo: O( X * log(log(X)) + N * M * 2 M ), donde X es el elemento más grande de la array
Espacio auxiliar: O(X + 2 M )