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
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.
Java
importjava.io.*;
importjava.lang.*;
importjava.util.*;
classGFG {
publicstaticbooleanprime(intnum)
{
for(inti = 2; i * i <= num; i++) {
if(num % i == 0) {
returnfalse;
}
}
returntrue;
}
publicstaticintcal(intn, intm)
{
intcount = 0;
for(inti = 2; i <= (n + m); i++) {
if(prime(i)) {
count++;
}
}
returncount;
}
publicstaticvoidmain(String[] args)
{
intN = 3, M = 4;
System.out.println(cal(N, M));
}
}
Time Complexity: O((N+M) * sqrt(N+M)) Auxiliary Space: O(1)
Denial of responsibility!FineRadar is an automatic aggregator around the global media. All the content are available free on Internet. We have just arranged it in one platform for educational purpose only. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials on our website, please contact us by email – [email protected]. The content will be deleted within 24 hours.
