Dadas dos arrays arr1[] y arr2[]. La tarea es encontrar el conteo de tales elementos en la primera array cuyo al menos un factor esté presente en la segunda array.
Ejemplos :
Input : arr1[] = {10, 2, 13, 4, 15} ; arr2[] = {2, 4, 5, 6}
Output : 4
There is no factor of 13 which is present in the
second array. Except 13, factors of the rest 4
elements of the first array is present in the
second array.
Input : arr1[] = {11, 13, 17, 15} ; arr2[] = {3, 7, 9, 5}
Output : 1
La idea es insertar todos los elementos de la segunda array en un hash de modo que la búsqueda de factores se pueda realizar en tiempo constante. Ahora, recorra la primera array y para cada elemento genere todos los factores a partir de 1 y verifique si alguno de los factores está presente en el hash o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find count of
// elements in first array whose
// atleast one factor is present
// in second array.
#include <bits/stdc++.h>
using namespace std;
// Util function to count the elements
// in first array whose atleast
// one factor is present in second array
int elementCount(int arr1[], int n1, int arr2[], int n2)
{
// counter to count number of elements
int count = 0;
// Hash of second array elements
unordered_set<int> hash;
for (int i = 0; i < n2; i++)
hash.insert(arr2[i]);
// loop to traverse through array elements
// and check for its factors
for (int i = 0; i < n1; i++) {
// generate factors of elements
// of first array
for (int j = 1; j * j <= arr1[i]; j++) {
// Check if j is a factor
if (arr1[i] % j == 0) {
// check if the factor is present in
// second array using the hash
if ((hash.find(j) != hash.end()) ||
(hash.find(arr1[i] / j) != hash.end())) {
count++;
break;
}
}
}
}
return count;
}
// Driver code
int main()
{
int arr1[] = { 10, 2, 13, 4, 15 };
int arr2[] = { 2, 4, 5, 6 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
cout << elementCount(arr1, n1, arr2, n2);
return 0;
}
Java
// Java program to find count of
// elements in first array whose
// atleast one factor is present
// in second array.
import java.util.*;
class GFG
{
// Util function to count the elements
// in first array whose atleast
// one factor is present in second array
static int elementCount(int arr1[], int n1,
int arr2[], int n2)
{
// counter to count number of elements
int count = 0;
// Hash of second array element
HashSet<Integer> hash = new HashSet<>();
for (int i = 0; i < n2; i++)
{
hash.add(arr2[i]);
}
// loop to traverse through array elements
// and check for its factors
for (int i = 0; i < n1; i++)
{
// generate factors of elements
// of first array
for (int j = 1; j * j <= arr1[i]; j++)
{
// Check if j is a factor
if (arr1[i] % j == 0)
{
// check if the factor is present in
// second array using the hash
if ((hash.contains(j) && j !=
(int) hash.toArray()[hash.size() - 1]) ||
(hash.contains(arr1[i] / j) && (arr1[i] / j) !=
(int) hash.toArray()[hash.size() - 1]))
{
count++;
break;
}
}
}
}
return count;
}
// Driver code
public static void main(String[] args)
{
int arr1[] = {10, 2, 13, 4, 15};
int arr2[] = {2, 4, 5, 6};
int n1 = arr1.length;
int n2 = arr2.length;
System.out.println(elementCount(arr1, n1, arr2, n2));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python program to find count of # elements in first array whose # atleast one factor is present # in second array. # Importing sqrt() function from math import sqrt # Util function to count the # elements in first array # whose atleast one factor is # present in second array def elementCount(arr1, arr2): # counter to count # number of elements count = 0 # Hash of second array elements hash = frozenset(arr2) # loop to traverse through array # elements and check for its factors for x in arr1: # generate factors of # elements of first array for j in range(1, int(sqrt(x)) + 1): # Check if j is a factor if x % j == 0: # check if the factor is present # in second array using the hash if (j in hash or x / j in hash): count+=1 break return count # Driver code arr1 = [ 10, 2, 13, 4, 15 ] arr2 = [ 2, 4, 5, 6 ] print(elementCount(arr1, arr2)) # This code is contributed # by vaibhav29498
C#
// C# program to find count of
// elements in first array whose
// atleast one factor is present
// in second array.
using System;
using System.Linq;
using System.Collections.Generic;
class GFG
{
// Util function to count the elements
// in first array whose atleast
// one factor is present in second array
static int elementCount(int []arr1, int n1,
int []arr2, int n2)
{
// counter to count number of elements
int count = 0;
// Hash of second array element
HashSet<int> hash = new HashSet<int>();
for (int i = 0; i < n2; i++)
{
hash.Add(arr2[i]);
}
// loop to traverse through array elements
// and check for its factors
for (int i = 0; i < n1; i++)
{
// generate factors of elements
// of first array
for (int j = 1; j * j <= arr1[i]; j++)
{
// Check if j is a factor
if (arr1[i] % j == 0)
{
// check if the factor is present in
// second array using the hash
if ((hash.Contains(j) && j !=
(int) hash.ToArray()[hash.Count- 1]) ||
(hash.Contains(arr1[i] / j) && (arr1[i] / j) !=
(int) hash.ToArray()[hash.Count - 1]))
{
count++;
break;
}
}
}
}
return count;
}
// Driver code
public static void Main(String[] args)
{
int []arr1 = {10, 2, 13, 4, 15};
int []arr2 = {2, 4, 5, 6};
int n1 = arr1.Length;
int n2 = arr2.Length;
Console.WriteLine(elementCount(arr1, n1, arr2, n2));
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP program to find count of
// elements in first array whose
// atleast one factor is present
// in second array.
// Util function to count the
// elements in first array
// whose atleast one factor is
// present in second array
function elementCount($arr1, $arr2)
{
// counter to count
// number of elements
$count = 0;
// Hash of second array elements
$hash = array_unique($arr2);
// loop to traverse through array
// elements and check for its factors
foreach($arr1 as &$x)
// generate factors of
// elements of first array
for ($j = 1; $j < (int)(sqrt($x)) + 1; $j++)
// Check if j is a factor
if ($x % $j == 0)
{
// check if the factor is present
// in second array using the hash
if (in_array($j, $hash) ||
in_array((int)($x / $j), $hash))
{
$count++;
break;
}
}
return $count;
}
// Driver code
$arr1 = array( 10, 2, 13, 4, 15 );
$arr2 = array( 2, 4, 5, 6 );
print(elementCount($arr1, $arr2));
// This code is contributed mits
?>
Javascript
<script>
// javascript program to find count of
// elements in first array whose
// atleast one factor is present
// in second array.
// Util function to count the elements
// in first array whose atleast
// one factor is present in second array
function elementCount(arr1 , n1 , arr2 , n2) {
// counter to count number of elements
var count = 0;
// Hash of second array element
var hash = new Set();
for (i = 0; i < n2; i++) {
hash.add(arr2[i]);
}
// loop to traverse through array elements
// and check for its factors
for (i = 0; i < n1; i++) {
// generate factors of elements
// of first array
for (j = 1; j * j <= arr1[i]; j++) {
// Check if j is a factor
if (arr1[i] % j == 0) {
// check if the factor is present in
// second array using the hash
if ((hash.has(j) && j != parseInt( hash[hash.length - 1])
|| (hash.has(arr1[i] / j) && (arr1[i] / j) != parseInt( hash[hash.length - 1])))) {
count++;
break;
}
}
}
}
return count;
}
// Driver code
var arr1 = [ 10, 2, 13, 4, 15 ];
var arr2 = [ 2, 4, 5, 6 ];
var n1 = arr1.length;
var n2 = arr2.length;
document.write(elementCount(arr1, n1, arr2, n2));
// This code contributed by umadevi9616
</script>
Salida :
4