Minimum number of operations required to make all elements of at least one row of given Matrix prime
Given a matrix, mat[][] of size N * M, the task is to find the minimum count of operations required to make all elements of at least one row of the given matrix prime. In each operation, merge any two rows of the matrix based on the following conditions:
- If kth elements of both rows of the matrix, i.e, mat[i][k] and mat[j][k] are prime numbers or composite numbers then kth element of the merged row contains min(mat[i][k], mat[j][k]).
- Otherwise, kth element of the merged row contains the element which is prime.
If it is not possible to get all elements of a row as prime numbers, then print -1.
Examples:
Input: mat[][] = { { 4, 6, 5 }, { 2, 9, 12 }, { 32, 7, 18 }, { 12, 4, 35 } }
Output: 2
Explanation:
Merging mat[0] and mat[1] modifies mat[][] to { { 2, 6, 5 }, { 32, 7, 18 }, { 12, 4, 35 } }
Merging mat[0] and mat[1] modifies mat[][] to { { 2, 7, 5 }, { 12, 4, 35 } }
Since first row of the matrix consists only of prime numbers, the required output is 2.Input: mat[][] = { {4, 6}, {8, 3} }
Output: -1
Explanation:
Merging mat[0] and mat[1] modifies mat[][] to { { 4, 3 } }
Since none of the elements in the row is prime, the required output is -1.
Approach:The problem can be solved using Dynamic programming with Bitmasks. Follow the steps below to solve the problem:
- Initialize a variable, say bitmask, where ith bit of bitmask stores if ith column of a row is a prime number or not.
- Initialize an array, say dp[], where dp[X] stores the minimum count of operations required to get X count of prime numbers in a row.
- Traverse each row of the matrix and update the value of bitmask for each row. Iterate over the range [(1 << (M – 1)), 0] using variable j and update the value of dp[j | bitmask] to min(dp[j | bitmask], dp[j] + 1).
- Finally, check if minimum count of operations required to get M prime numbers in a row is greater than N or not i.e, check if dp[(1 << (M – 1))] is greater than N or not. If found to be true, then print -1.
- Otherwise, print the value of (dp[(1 << (M – 1))] – 1).
Below is the implementation of the above approach.
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> |
3
Time Complexity: O( X * log(log(X)) + N * M * 2M), where X is largest element of the matrix
Auxiliary Space: O(X + 2M)
Contact Us