Data Modelling & AI Data Structure & Algorithm

Minimum number of operations required to make all elements of at least one row of given Matrix prime

23 June 2025

0

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 k^th elements of both rows of the matrix, i.e, mat[i][k] and mat[j][k] are prime numbers or composite numbers then k^th element of the merged row contains min(mat[i][k], mat[j][k]).
Otherwise, k^th 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 i^th bit of bitmask stores if i^th 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>

Output:

Time Complexity: O( X * log(log(X)) + N * M * 2^M), where X is largest element of the matrix
Auxiliary Space: O(X + 2^M)

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!

Minimum number of operations required to make all elements of at least one row of given Matrix prime

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

Is the Oura Ring 4 Ceramic worth buying? I’ve worn it to find out

Pixel Tablet’s biggest weakness isn’t performance — it’s its USB port

Motorola’s new thin flagship will take on the Galaxy S25 Edge and iPhone Air at their own game

Google TV wants to take your video-watching experience to the next level with a bunch of AI features

EDITOR PICKS

Is the Oura Ring 4 Ceramic worth buying? I’ve worn it to find out

Pixel Tablet’s biggest weakness isn’t performance — it’s its USB port

Motorola’s new thin flagship will take on the Galaxy S25 Edge and iPhone Air at their own game

POPULAR POSTS

Is the Oura Ring 4 Ceramic worth buying? I’ve worn it to find out

Pixel Tablet’s biggest weakness isn’t performance — it’s its USB port

Motorola’s new thin flagship will take on the Galaxy S25 Edge and iPhone Air at their own game

POPULAR CATEGORY

ABOUT US

FOLLOW US