Count the Possible Sets Using Integers from a Range [2, N] Using Given Operations that are in Equivalence Relation

Approach

• The idea to solve the problem is primarily based on the subsequent observation that all the numbers less than or same to N/2 belong to the same set because if 2 is multiplied in them, they may be an even number and have GCD greater than 1 with 2.
• So the remaining sets are formed by numbers greater than N/2 and are prime because if they are not prime, then there may be a number less than or same as N/2, which will be the divisor of that particular number. 
• The prime numbers from the range 2 to N can be found using Sieve Eratosthenes.

Implementation

import java.util.*;

class Solution{

     static boolean sieve[] = new boolean[100001];

          // To find the prime numbers equal or less than n
          static void Eratosthenes(int n)
          {
                Arrays.fill(sieve, true);

               for(int i = 2; i * i <= n; i++)
               {
                    if (sieve[i] == true)
                    {
                       for(int j = i * i; j <= n; j += i)
                         sieve[j] = false;
                    }
                }
          }

    // To count the number of sets
    static void NumberofSets(int N)
    {
        Eratosthenes(N);


        if (N == 2)
        {
          System.out.print(1);
        }
       else if (N == 3)
       {
         System.out.print(2);
       }
       else
       {

       // Set has integers less than or equal to n/2
       int total = 1;


      for(int i = N / 2 + 1; i <= N; i++)
      {

         // If the number is prime
         // Increment answer by 1
         if (sieve[i])
         {
            total += 1;
         }
       }
         System.out.print(total);
   }
 }

  // Main function
  public static void main(String[] args)
  {


      int N = 9;


     NumberofSets(N);
  }
}

Output

3

Complexity Analysis

Time Complexity:

The time complexity to solve the above approach is O(N), where N is the integer given is the question.

Space Complexity:

The space complexity is O(100001) due to the initialization of an array of size 10001.

Check out this problem - Two Sum Problem

FAQs

1. What is the use of the Sieve of Eratosthenes algorithm?
   This algorithm is used to print all the prime numbers equal to or less than n.
    
2. What is the time complexity of this approach?
   The time complexity to solve the above approach is O(N), where N is the integer given is the question.
    
3. What do you mean by GCD?
   The greatest common factor(GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each integer.
   For example, GCD(4,8) is 4.

Key Takeaways

This blog has covered the following things:

• What is the meaning of the GCD and equivalence relation?
• What is our aim for generating the output, along with some examples?
• Approach and the implementation of the question in the Java language.

Before stepping into this problem, you can try problems similar to this concept like 

GCD, Max GCD Pair, and many more.

Coding Ninjas Studio is a one-stop destination for various DSA questions typically asked in interviews to practice more such problems.

Keep Learning, Keep Growing!!!