Dada una array arr[] que consta de N enteros positivos distintos y un rango [L, R] , la tarea es encontrar el elemento en el rango dado [L, R] que son coprimos con todos los elementos de la array .
Ejemplos:
Entrada: L = 3, R = 11, arr[ ] = {4, 7, 9, 6, 13, 21}
Salida: { 5, 11 }
Explicación:
Los elementos en el rango [3, 5] que son coprimos con todos los elementos de la array son {5, 11}.Entrada: L = 1, R = 10, arr[ ] = {3, 5}
Salida: {1, 2, 4, 7, 8}
Enfoque: el problema dado se puede resolver almacenando todos los divisores de cada elemento de array en un HashSet . Deje que haya otro HashSet , digamos S que consta de números en el rango [L, R] ahora la tarea es eliminar los múltiplos de los divisores calculados a partir de este HashSet S para obtener los números resultantes. Siga los pasos para resolver el problema:
- Almacene los divisores de cada elemento de la array en un conjunto desordenado , digamos S.
- Almacene todos los valores en el rango [L, R] en otro HashSet, digamos M .
- Atraviese el conjunto desordenado S y, para cada elemento de S , diga value , elimine todos los múltiplos de value del conjunto M si está presente en M.
- Después de completar los pasos anteriores, imprima todos los elementos almacenados en HashSet M como los números resultantes requeridos.
A continuación se muestra la implementación del enfoque anterior:
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
Producción:
8 7 2 1 4
Complejidad de tiempo: O(N*sqrt(M)), donde M es el número máximo de elementos de la array .
Espacio auxiliar: O(max(R – L, N))
Publicación traducida automáticamente
Artículo escrito por aniket173000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA