Find numbers in the range [L, R] that are coprime with all given Array elements

Introduction 

Problem statement

We are given an array having N distinct positive integers and a range [L, R]. Our task is to find all the elements in the range [L, R] that are coprime with all given array elements in the given array.

Let us revisit what are coprime numbers:

Coprime Numbers

• A pair of numbers are coprime if they do not have any common factor other than 1. 
• There should be at least 2 numbers to form a set of coprime numbers. For example, (5, 6), (7, 9), (3, 7) etc.

Sample test cases

Example 1:

Input: a[] = { 5, 6, 8, 9, 11, 2, 18 }, L = 5, R = 10
Output: 7

Explanation
{7} is the only element in the range of L to R, which is coprime with all given array elements

Example 2:

Input: a[] = { 7, 9, 4, 11, 22, 13, 16, 8, 24 }, L = 4, R = 18
Output: 17 5

Explanation
{17,5} are the elements in the range of L to R, which are coprime with all given array elements

Approach

The idea is simple, calculate all the divisors for every array element and store it in a container. Traverse the container and for every divisor, remove all the multiples of it from the range [L, R]. Finally, print all the numbers after removing every divisor's multiples from the range [L, R].

We will use an unordered set to store all the divisors for every array element.

Steps of algorithm

• Store all the divisors for every array element in an unordered set and remove 1 from it, say DIV.
• Store all the numbers in the range [L, R] in another unordered set, say NUMS.
• Traverse the unordered set DIV and for each element, remove all the multiples of that element from the NUMS if it is present in NUMS.
• Print all the numbers present in NUMS, which are coprime with all given array elements.
   

Let’s understand the above approach with an example:

Given array = { 7, 9, 4, 11, 22, 13, 16, 8, 24 }, L = 4, R = 18

Steps:

• Store all the divisors for every element in DIV and remove 1 from DIV.

Divisors of 7 = {1, 7}

Divisors of 9 = {1, 3, 9}

Divisors of 4 = {1, 2, 4}

Divisors of 11 = {1, 11}

Divisors of 22 = {1, 2, 11, 22}

Divisors of 13 = {1, 13}

Divisors of 16 = {1, 2, 4, 8, 16}

Divisors of 8 = {1, 2, 4, 8}

Divisors of 24 = {1, 2, 3, 4, 6, 8, 12, 24}

DIV = { 6, 12, 8, 3, 9, 7, 24, 4, 2, 13, 11, 22, 16 }
 

• Store all the numbers from L to R in NUMS.

NUMS = { 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 }
 

• Remove all the multiples of every element in DIV from NUMS.
   

After removing the multiples, NUMS = { 5, 17 }

• Print all the numbers present in NUMS, which are coprime with all given array elements.
   

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

void coprime_with_array(int a[], int n, int L, int R)
{
    unordered_set<int> DIV;

    for (int i = 0; i < n; i++)
    {
        int elem = a[i];

        for (int j = 1; j <= sqrt(elem) + 1; j++)
        {
            if (elem % j == 0)
            {
                DIV.insert(j);
                DIV.insert(elem / j);
            }
        }
    }

    unordered_set<int> NUMS;

    for (int i = L; i <= R; i++)
        NUMS.insert(i);

    DIV.erase(1);

    for (auto x : DIV)
    {
        int i = 1;

        while (i * x <= R)
        {
            NUMS.erase(i * x);

            i++;
        }
    }

    for (auto x : NUMS)
    {
        cout << x << " ";
    }
}

int main()
{
    int a[] = { 7, 9, 4, 11, 22, 13, 16, 8, 24 };

    int L = 4, R = 18;

    int N = sizeof(a) / sizeof(a[0]);

    coprime_with_array(a, N, L, R);

    return 0;
}

Output

17 5

Complexity Analysis

Time complexity: O(n * sqrt(maxm)), as we are running a nested loop of size n and maxm, where n is the number of elements and maxm is the maximum number present in the given array.

Space complexity: O(max(R-L, n)), as we are using unordered sets of sizes n and R-L.

Frequently Asked Questions

Q1. What do you mean by co-prime numbers?

Answer: Co-Prime Numbers are a collection of numbers that share no common factor other than one. This indicates that their HCF (Highest Common Factor) is 1. In order to form Co-Primes, there must be at least two Numbers. Coprime numbers are also known as relatively prime numbers.
 

Q2. How do you find all divisors of a number?

Answer: Exhaustive trial division is the most basic method for calculating divisors. To find the positive divisors for an integer n, divide n by each of the integers 1, 2, 3,..., n, and the ones that divide evenly form the set of positive divisors for n.
 

Q3. How to check if a set contains an element in C++?

Answer: The member function find() is used to check for the existence of an element in the set container (std::set or std::unordered set). If the specified element can be found, an iterator is returned; otherwise, an iterator to the container's end is returned.

Q4. In C++, how do you traverse a set?

Answer: Using Iterators to Iterate over a Set,

set::begin() returns an iterator that points to the set's first element.

On the other hand, set::end() returns an iterator that continues past the end of the set. 

To iterate a set forward, we must first create an iterator and then initialise it with set::begin ().

Key Takeaways

This article discussed the approach to finding the numbers in the range [L, R] that are coprime with all given array elements with complete explanation, examples for a better understanding and its implementation in C++.

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Thank you for reading!