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.
- Check whether the current number is prime or not.
- 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 notbool 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 subsetint 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 Codeint 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 approachimport 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 notdef 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 subsetdef 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 CodeN = 3M = 4# Function callprint(cal(N, M))# This code is contributed by lokesh. |
C#
// C# code to implement the approachusing 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 notfunction 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 subsetfunction 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:
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
