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

Sandeep kamila
Last Updated: May 13, 2022

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.
     
Element in DIV (N)All multiples of N <= R
66, 12, 18
1212
88, 16
33, 6, 9, 12, 15, 18
99, 18
77, 14
24 
44, 8, 12, 16
22, 4, 6, 8, 10, 12, 14, 16, 18
1313
1111
22 
1616

 

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!

Was this article helpful ?
0 upvotes