Find numbers in range [L, R] that are coprime with given Array elements
Given an array arr[] consisting of N distinct positive integers and a range [L, R], the task is to find the element in the given range [L, R] that are coprime with all array elements.
Examples:
Input: L = 3, R = 11, arr[ ] = {4, 7, 9, 6, 13, 21}
Output: {5, 11}
Explanation:
The elements in the range [3, 5] which are co prime with all array elements are {5, 11}.Input: L = 1, R = 10, arr[ ] = {3, 5}
Output: {1, 2, 4, 7, 8}
Approach: The given problem can be solved by storing all the divisors of every array element in a HashSet. Let there be another HashSet, say S consisting of numbers in the range [L, R] now the task is to remove the multiples of the divisors calculated from this HashSet S to get the resultant numbers. Follow the steps to solve the problem:
- Store the divisors of every array element in an unordered set, say S.
- Store all the values in the range [L, R] in another HashSet, say M.
- Traverse the unordered set S and for each element in S, say value remove all the multiples of value from the set M if it is present in M.
- After completing the above steps, print all the elements stored in HashSet M as the required resultant numbers.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find all the elements in // the range [L, R] which are co prime // with all array elements void elementsCoprimeWithArr( int A[], int N, int L, int R) { // Store all the divisors of array // element in S unordered_set< int > S; // Find the divisors for ( int i = 0; i < N; i++) { int curr_ele = A[i]; for ( int j = 1; j <= sqrt (curr_ele) + 1; j++) { if (curr_ele % j == 0) { S.insert(j); S.insert(curr_ele / j); } } } // Stores all possible required number // satisfying the given criteria unordered_set< int > store; // Insert all element [L, R] for ( int i = L; i <= R; i++) store.insert(i); S.erase(1); // Traverse the set for ( auto it : S) { int ele = it; int index = 1; // Remove the multiples of ele while (index * ele <= R) { store.erase(index * ele); index++; } } // Print the resultant numbers for ( auto i : store) { cout << i << " " ; } } // Driver Code int main() { int arr[] = { 3, 5 }; int L = 1, R = 10; int N = sizeof (arr) / sizeof (arr[0]); elementsCoprimeWithArr(arr, N, L, R); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find all the elements in // the range [L, R] which are co prime // with all array elements static void elementsCoprimeWithArr( int A[], int N, int L, int R) { // Store all the divisors of array // element in S HashSet<Integer> S = new HashSet<Integer>(); // Find the divisors for ( int i = 0 ; i < N; i++) { int curr_ele = A[i]; for ( int j = 1 ; j <= Math.sqrt(curr_ele) + 1 ; j++) { if (curr_ele % j == 0 ) { S.add(j); S.add(curr_ele / j); } } } // Stores all possible required number // satisfying the given criteria HashSet<Integer> store= new HashSet<Integer>(); // Insert all element [L, R] for ( int i = L; i <= R; i++) store.add(i); S.remove( 1 ); // Traverse the set for ( int it : S) { int ele = it; int index = 1 ; // Remove the multiples of ele while (index * ele <= R) { store.remove(index * ele); index++; } } // Print the resultant numbers for ( int i : store) { System.out.print(i+ " " ); } } // Driver Code public static void main(String[] args) { int arr[] = { 3 , 5 }; int L = 1 , R = 10 ; int N = arr.length; elementsCoprimeWithArr(arr, N, L, R); } } // This code is contributed by shikhasingrajput |
Python3
# python 3 program for the above approach import math # Function to find all the elements in # the range [L, R] which are co prime # with all array elements def elementsCoprimeWithArr( A, N, L, R): # Store all the divisors of array # element in S S = [] # Find the divisors for i in range (N): curr_ele = A[i] for j in range ( 1 , ( int )(math.sqrt(curr_ele)) + 1 ): if (curr_ele % j = = 0 ): S.append(j) S.append(curr_ele / / j) # Stores all possible required number # satisfying the given criteria store = [] S = set (S) # Insert all element [L, R] for i in range (L, R + 1 ): store.append(i) S.remove( 1 ) # / Traverse the set for it in S: ele = it index = 1 # Remove the multiples of ele while (index * ele < = R): store.remove(index * ele) index + = 1 # Print the resultant numbers for i in store: print (i, end = " " ) # Driver Code if __name__ = = "__main__" : arr = [ 3 , 5 ] L = 1 R = 10 N = len (arr) elementsCoprimeWithArr(arr, N, L, R) # This code is contributed by ukasp. |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find all the elements in // the range [L, R] which are co prime // with all array elements static void elementsCoprimeWithArr( int []A, int N, int L, int R) { // Store all the divisors of array // element in S HashSet< int > S = new HashSet< int >(); // Find the divisors for ( int i = 0; i < N; i++) { int curr_ele = A[i]; for ( int j = 1; j <= Math.Sqrt(curr_ele) + 1; j++) { if (curr_ele % j == 0) { S.Add(j); S.Add(curr_ele / j); } } } // Stores all possible required number // satisfying the given criteria HashSet< int > store= new HashSet< int >(); // Insert all element [L, R] for ( int i = L; i <= R; i++) store.Add(i); S.Remove(1); // Traverse the set foreach ( int it in S) { int ele = it; int index = 1; // Remove the multiples of ele while (index * ele <= R) { store.Remove(index * ele); index++; } } // Print the resultant numbers foreach ( int i in store) { Console.Write(i+ " " ); } } // Driver Code public static void Main(String[] args) { int []arr = { 3, 5 }; int L = 1, R = 10; int N = arr.Length; elementsCoprimeWithArr(arr, N, L, R); } } // This code is contributed by shikhasingrajput |
Javascript
// JS function for the above approach function elementsCoprimeWithArr(A, N, L, R) { // Store all the divisors of array element in S let S = new Set(); // Find the divisors for (let i = 0; i < N; i++) { let curr_ele = A[i]; for (let j = 1; j <= Math.sqrt(curr_ele) + 1; j++) { if (curr_ele % j === 0) { S.add(j); S.add(curr_ele / j); } } } // Stores all possible required number satisfying the given criteria let store = new Set(); // Insert all element [L, R] for (let i = L; i <= R; i++) store.add(i); S. delete (1); // Traverse the set for (let it of S) { let ele = it; let index = 1; // Remove the multiples of ele while (index * ele <= R) { store. delete (index * ele); index++; } } // Print the resultant numbers for (let i of store) { console.log(i); } } // Driver Code let arr = [3, 5]; let L = 1, R = 10; let N = arr.length; elementsCoprimeWithArr(arr, N, L, R); |
8 7 2 1 4
Time Complexity: O(N*sqrt(M)), where M is the maximum array elements.
Auxiliary Space: O(max(R – L, N))
Contact Us