1.
Introduction
2.
Problem Statement
3.
Approach
4.
Implementation
5.
Complexity Analysis
5.1.
Time Complexity:
5.2.
Space Complexity:
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

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

## Introduction

Data Structures play a vital role in developing our problem-solving skills to crack the interview rounds of product-based companies.

We must print the number of sets formed in an Equivalence relation from a range[2, N] using given operations.

Before heading towards the problem, certain words should be clear in your head for thinking it in that way.

What do you understand by Equivalence Relation?

An equivalence relation is Reflexive, Symmetric, and Transitive.

Reflexive Property

This property states that for every real number a, a=a.

Symmetric Property

This property states that for all real numbers a and b, if a=b, then b=a.

Transitive Property

This property states that for all real numbers a, b, and c, if a=b and b=c, then a=c.

What do you mean by GCD of two numbers?

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.

Let's move to our problem statement for more clarity.

Also see, Euclid GCD Algorithm

## Problem Statement

We will be provided with an integer 'N' as input where we have to choose integers(distinct) from the range [2 to N], if their GCD is greater than '1', then insert them into the same set as long as we find such integers. The sets formed will follow the equivalence properties, which states that if x and y are in the same set and y and z are in the same set, then x and z should be in the same set.

We have to print the count of the total sets formed.

Let's clear this mess with the help of an example.

Example 1:

Input: N= 5

Output: 2

Explanation: Integers from the range [2, N] are {2,3,4,5}, Here GCD of 2,3 is '1', so they can't be the same set. GCD of 2,4 is '2', so they can be in the same set. GCD of 3,5 is '1', so they can be in the same set. Hence the two sets formed will be {2,4} and {3,5}.

Example 2:

Input: N=9

Output: 3

Explanation: Integers from range [2,N] are {2,3,4,5,6,7,8,9}. Here the GCD of integers {2,4,6,8} are 2 and the GCD of integers {3,6,9} are 3 and GCD of {5} and {7} is ‘1’. But as we know that sets are in equivalence relation. So, according to the transitivity property, integer '6' is common in both sets. Hence all the integers of both sets lie in one set. As the question says, a set should contain two more distinct integers whose GCD is greater than '1' but 5 and 7 have gcd as 1. Therefore they will be in different sets.

The total sets will be: {2,3,4,6,8,9}, {5}, {7}.

Now that we have understood the question let's move towards our approach and implementation.

## 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
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

GCDMax 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!!!

Live masterclass