Horje
Maximize size of Subset from Matrix values such that any pair is coprime

Given two integers N and M which denotes a matrix of size N*M that has the value of each cell as the sum of its row number and column number, the task is to find the maximum size of a subset that can be formed using the elements of this matrix such that any pair of the subset will be coprime to each other.   

Examples:

Input: N = 3, M = 4
Output: 4
Explanation: There are a maximum of 4 possible numbers on the matrix, Which are: {2, 5, 7, 3}, This makes pairs with the combination itself and has the GCD of that pair equal to one. i, e. (2, 3), (2, 5), (5, 3) . . . The matrix is shown below

2 3 4 5
3 4 5 6
4 5 6 7

Input: N = 5, M = 8
Output: 6

Approach: The problem can be solved based on the following observation

As any pair of the subset will be coprime to each other, therefore the subset will be formed using all the prime within the range [2, N+M].

Follow the steps mentioned below to implement the idea:

  • Create a function to check if a number is prime or not.
  • Run a loop from i = 2 to N+M.
    • Check whether the current number is prime or not.
      • If yes then increment the counter variable.
  • Last, return the count of primes as the answer.

Below is the Implementation of the above approach.

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Boolean function to check a number is prime or not
bool prime(int num)
{
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
 
// Function to find the size of the subset
int cal(int n, int m)
{
    // Variable to count pairs
    int count = 0;
 
    // Loop for traversing 2 to (N+M)
    for (int i = 2; i <= (n + m); i++) {
 
        // Checking if current number
        // of matrix is prime or not
        if (prime(i)) {
 
            // Incrementing count variable
            count++;
        }
    }
 
    // Return maximum number of pairs
    return count;
}
 
// Driver Code
int main()
{
    int N = 3, M = 4;
 
    // Function call
    cout << cal(N, M);
    return 0;
}
 
// This code is contributed by Rohit Pradhan

Java

// Java code to implement the approach
 
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
    // Boolean function to check a number is prime or not
    public static boolean prime(int num)
    {
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
 
    // Function to find the size of the subset
    public static int cal(int n, int m)
    {
        // Variable to count pairs
        int count = 0;
 
        // Loop for traversing 2 to (N+M)
        for (int i = 2; i <= (n + m); i++) {
 
            // Checking if current number
            // of matrix is prime or not
            if (prime(i)) {
 
                // Incrementing count variable
                count++;
            }
        }
 
        // Return maximum number of pairs
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 3, M = 4;
 
        // Function call
        System.out.println(cal(N, M));
    }
}

Python3

# Python code for the above approach
 
# Function to check a number is prime or not
def prime(num):
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    return True
 
# Function to find the size of the subset
def cal(n, m):
    # Variable to count pairs
    count = 0
 
    # Loop for traversing 2 to (N+M)
    for i in range(2, n+m+1):
        # Checking if current number
        # of matrix is prime or not
        if prime(i):
            # Incrementing count variable
            count += 1
 
    # Return maximum number of pairs
    return count
 
# Driver Code
N = 3
M = 4
 
# Function call
print(cal(N, M))
 
# This code is contributed by lokesh.

C#

// C# code to implement the approach
using System;
 
class GFG {
 
  // Boolean function to check a number is prime or not
  public static bool prime(int num)
  {
    for (int i = 2; i * i <= num; i++) {
      if (num % i == 0) {
        return false;
      }
    }
    return true;
  }
 
  // Function to find the size of the subset
  public static int cal(int n, int m)
  {
    // Variable to count pairs
    int count = 0;
 
    // Loop for traversing 2 to (N+M)
    for (int i = 2; i <= (n + m); i++) {
 
      // Checking if current number
      // of matrix is prime or not
      if (prime(i)) {
 
        // Incrementing count variable
        count++;
      }
    }
 
    // Return maximum number of pairs
    return count;
  }
 
  // Driver Code
  static public void Main()
  {
    int N = 3, M = 4;
 
    // Function call
    Console.Write(cal(N, M));
  }
}
 
// This code is contributed by Pushpesh Raj.

Javascript

// Javascript code to implement the approach
 
// Boolean function to check a number is prime or not
function prime(num)
{
    for (let i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
 
// Function to find the size of the subset
function cal(n, m)
{
    // Variable to count pairs
    let count = 0;
 
    // Loop for traversing 2 to (N+M)
    for (let i = 2; i <= (n + m); i++) {
 
        // Checking if current number
        // of matrix is prime or not
        if (prime(i)) {
 
            // Incrementing count variable
            count++;
        }
    }
 
    // Return maximum number of pairs
    return count;
}
 
// Driver Code
    let N = 3, M = 4;
 
    // Function call
    document.write(cal(N, M));

Output

4

Time Complexity: O((N+M) * sqrt(N+M))
Auxiliary Space: O(1)

Related Articles:


 


Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Divide two number using Binary search without using any / and % operator Divide two number using Binary search without using any / and % operator
Maximum multiple of a number with all digits same Maximum multiple of a number with all digits same
Check if given vectors are Parallel or Perpendicular? Check if given vectors are Parallel or Perpendicular?
Maximize the money when no two adjacent Array indices can be chosen Maximize the money when no two adjacent Array indices can be chosen
12 hour clock Multiplication 12 hour clock Multiplication

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 16



 

Horje