Elementos de un arreglo que no son divisibles por ningún elemento de otro arreglo

Dados dos arreglos A[] y B[], escriba un código eficiente para determinar si cada elemento de B[] es divisible por al menos 1 elemento de A[]. Muestra los elementos de B[] que no son divisibles por ninguno de los elementos de A[]. 

Ejemplos: 

Input : A[] = {100, 200, 400, 100, 600}
        B[] = {45, 90, 48, 1000, 3000}
Output : 45, 90, 48 
The output elements are those that are 
not divisible by any element of A[].

Método I (Implementación ingenua):

• Iterar a través de cada elemento de B[].
• Comprueba si es divisible por al menos 1 elemento de A[] o no. Si no es divisible por ninguno, imprímelo.

Implementación:

// C++ code for naive implementation
#include<iostream>
using namespace std;
 
// Function for checking the condition
// with 2 loops
void printNonDivisible(int A[], int B[],
                          int n, int m)
{
    for (int i = 0; i < m; i++)
    {
        int j = 0;
        for (j = 0; j < n; j++)
            if( B[i] % A[j] == 0 )
                break;
 
        // If none of the elements in A[]
        // divided B[i]
        if (j == n)
            cout << B[i] << endl;
    }
}
 
// Driver code
int main()
{
    int A[] = {100, 200, 400, 100};
    int n = sizeof(A)/sizeof(A[0]);
    int B[] = {190, 200, 87, 600, 800};
    int m = sizeof(B)/sizeof(B[0]);
    printNonDivisible(A, B, n, m);
    return 0;
}

// Java code for naive implementation
import java.io.*;
 
public class GFG {
     
// Function for checking the condition
// with 2 loops
static void printNonDivisible(int []A, int []B,
                              int n, int m)
{
     
    for (int i = 0; i < m; i++)
    {
        int j = 0;
        for (j = 0; j < n; j++)
            if( B[i] % A[j] == 0 )
                break;
 
        // If none of the elements
        // in A[] divided B[i]
        if (j == n)
            System.out.println(B[i]);
    }
}
 
    // Driver code
    static public void main (String[] args)
    {
        int []A = {100, 200, 400, 100};
        int n = A.length;
         
        int []B = {190, 200, 87, 600, 800};
        int m = B.length;
         
        printNonDivisible(A, B, n, m);
    }
}
 
// This code is contributed by vt_m .

# Python3 code for naive implementation
import math as mt
 
# Function for checking the condition
# with 2 loops
def printNonDivisible(A, B, n, m):
 
    for i in range(m):
        j = 0
        for j in range(n):
            if(B[i] % A[j] == 0):
                break
 
        # If none of the elements in A[]
        # divided B[i]
        if (j == n - 1):
            print(B[i])
 
# Driver code
A = [100, 200, 400, 100]
n = len(A)
B = [190, 200, 87, 600, 800]
m = len(B)
printNonDivisible(A, B, n, m)
 
# This code is contributed by#
# mohit kumar 29

// C# code for naive implementation
using System;
 
public class GFG {
     
// Function for checking the
// condition with 2 loops
static void printNonDivisible(int []A, int []B,
                              int n, int m)
{
     
    for (int i = 0; i < m; i++)
    {
        int j = 0;
        for (j = 0; j < n; j++)
            if( B[i] % A[j] == 0 )
                break;
 
        // If none of the elements
        // in A[] divided B[i]
        if (j == n)
            Console.WriteLine(B[i]);
    }
}
 
    // Driver code
    static public void Main ()
    {
        int []A = {100, 200, 400, 100};
        int n = A.Length;
        int []B = {190, 200, 87, 600, 800};
        int m = B.Length;
        printNonDivisible(A, B, n, m);
    }
}
 
// This code is contributed by vt_m .

<?php
// PHP code for naive implementation
 
// Function for checking
// the condition with 2 loops
function printNonDivisible($A, $B,
                           $n, $m)
{
    for ($i = 0; $i < $m; $i++)
    {
        $j = 0;
        for ($j = 0; $j < $n; $j++)
            if( $B[$i] % $A[$j] == 0 )
                break;
 
        // If none of the elements
        // in A[] divided B[i]
        if ($j == $n)
            echo $B[$i], "\n";
    }
}
 
// Driver code
$A= array (100, 200, 400, 100);
$n = sizeof($A);
$B = array (190, 200, 87, 600, 800);
$m = sizeof($B);
 
printNonDivisible($A, $B, $n, $m);
 
// This code is contributed by ajit
?>

<script>
 
    // Javascript code for naive implementation
     
    // Function for checking the
    // condition with 2 loops
    function printNonDivisible(A, B, n, m)
    {
 
        for (let i = 0; i < m; i++)
        {
            let j = 0;
            for (j = 0; j < n; j++)
                if( B[i] % A[j] == 0 )
                    break;
 
            // If none of the elements
            // in A[] divided B[i]
            if (j == n)
                document.write(B[i] + "</br>");
        }
    }
     
    let A = [100, 200, 400, 100];
    let n = A.length;
    let B = [190, 200, 87, 600, 800];
    let m = B.length;
    printNonDivisible(A, B, n, m);
 
</script>

190
87

Complejidad de tiempo :- O(n*m) 
Espacio auxiliar :- O(1) 

Método 2 (Eficiente cuando los elementos son pequeños) 

• Mantenga una array mark[] para marcar los múltiplos de los números en A[].
• Marque todos los múltiplos de todos los elementos en A[], hasta un máximo de B[].
• Compruebe si el valor de marca[B[i]] para cada elemento n en B[] no es 0 e imprima si no está marcado.

Implementación:

// CPP code for improved implementation
#include<bits/stdc++.h>
using namespace std;
 
// Function for printing all elements of B[]
// that are not divisible by any element of A[]
void printNonDivisible(int A[], int B[], int n,
                                         int m)
{
    // Find maximum element in B[]
    int maxB = 0;
    for (int i = 0; i < m; i++)
        if (B[i] > maxB)
            maxB = B[i];
 
    // Initialize all multiples as marked
    int mark[maxB];
    memset(mark, 0, sizeof(mark));
 
    // Marking the multiples of all the
    // elements of the array.
    for (int i = 0; i < n; i++)
        for (int x = A[i]; x <= maxB; x += A[i])
            mark[x]++;
 
    // Print not marked elements
    for (int i = 0; i < m; i++)
        if (! mark[B[i]])
            cout << B[i] << endl;
}
 
// Driver function
int main()
{
    int A[] = {100, 200, 400, 100};
    int n = sizeof(A)/sizeof(A[0]);
    int B[] = {190, 200, 87, 600, 800};
    int m = sizeof(B)/sizeof(B[0]);
    printNonDivisible(A, B, n, m);
    return 0;
}

// Java code for improved implementation
import java.io.*;
 
class GFG
{
     
// Function for printing all elements of B[]
// that are not divisible by any element of A[]
static void printNonDivisible(int []A, int []B,
                                    int n,int m)
{
    // Find maximum element in B[]
    int maxB = 0;
    for (int i = 0; i < m; i++)
        if (B[i] > maxB)
            maxB = B[i];
 
    // Initialize all multiples as marked
 
    int [] mark = new int[maxB + 1];
    for(int i = 0; i < maxB; i++)
        mark[i]=0;
 
    // Marking the multiples of all the
    // elements of the array.
    for (int i = 0; i < n; i++)
        for (int x = A[i]; x <= maxB; x += A[i])
            mark[x]++;
 
    // Print not marked elements
    for (int i = 0; i < m; i++)
        if (mark[B[i]] == 0)
            System.out.println(B[i]);
}
 
// Driver code
static public void main(String[] args)
{
    int []A= {100, 200, 400, 100};
    int n = A.length;
    int []B= {190, 200, 87, 600, 800};
    int m = B.length;
    printNonDivisible(A, B, n, m);
}
}
 
// This code is contributed by Mohit Kumar.

# Python 3 code for improved implementation
 
# Function for printing all elements of B[]
# that are not divisible by any element of A[]
def printNonDivisible(A, B, n, m):
     
    # Find maximum element in B[]
    maxB = 0
    for i in range(0, m, 1):
        if (B[i] > maxB):
            maxB = B[i]
 
    # Initialize all multiples as marked
    mark = [0 for i in range(maxB)]
 
    # Marking the multiples of all
    # the elements of the array.
    for i in range(0, n, 1):
        for x in range(A[i], maxB, A[i]):
            mark[x] += 1
 
    # Print not marked elements
    for i in range(0, m - 1, 1):
        if (mark[B[i]] == 0):
            print(B[i])
 
# Driver Code
if __name__ == '__main__':
    A = [100, 200, 400, 100]
    n = len(A)
    B = [190, 200, 87, 600, 800]
    m = len(B)
    printNonDivisible(A, B, n, m)
 
# This code is contributed by
# Shashank_Sharma

// C# code for improved implementation
using System;
 
class GFG
{
     
// Function for printing all elements of []B
// that are not divisible by any element of []A
static void printNonDivisible(int []A, int []B,
                                    int n, int m)
{
    // Find maximum element in []B
    int maxB = 0;
    for (int i = 0; i < m; i++)
        if (B[i] > maxB)
            maxB = B[i];
 
    // Initialize all multiples as marked
    int [] mark = new int[maxB + 1];
    for(int i = 0; i < maxB; i++)
        mark[i] = 0;
 
    // Marking the multiples of all the
    // elements of the array.
    for (int i = 0; i < n; i++)
        for (int x = A[i]; x <= maxB; x += A[i])
            mark[x]++;
 
    // Print not marked elements
    for (int i = 0; i < m; i++)
        if (mark[B[i]] == 0)
            Console.WriteLine(B[i]);
}
 
// Driver code
static public void Main(String[] args)
{
    int []A= {100, 200, 400, 100};
    int n = A.Length;
    int []B= {190, 200, 87, 600, 800};
    int m = B.Length;
    printNonDivisible(A, B, n, m);
}
}
 
// This code is contributed by Rajput-Ji

<?php
// PHP code for improved implementation
 
// Function for printing all elements of B[]
// that are not divisible by any element of A[]
function printNonDivisible($A, $B, $n, $m)
{
     
    // Find maximum element in B[]
    $maxB = 0;
    for ($i = 0; $i < $m; $i++)
    {
        if ($B[$i] > $maxB)
            $maxB = $B[$i];
    }
     
    // Initialize all multiples as marked
    $mark = array();
    for ($i = 0; $i < $maxB; $i++)
    {
        $mark[] = "0";
    }
 
    // Marking the multiples of all
    // the elements of the array.
    for ($i = 0; $i < $n; $i++)
    {
        for ($x = $A[$i]; $x < $maxB;
                          $x += $A[$i])
        {
            $mark[$x] += 1;
        }
    }
     
    // Print not marked elements
    for ($i = 0; $i < $m - 1; $i++)
    {
        if ($mark[$B[$i]] == 0)
            echo "$B[$i]\n";
    }
}
 
// Driver Code
$A = array(100, 200, 400, 100);
$n = count($A);
$B = array(190, 200, 87, 600, 800);
$m = count($B);
printNonDivisible($A, $B, $n, $m);
 
// This code is contributed by
// Srathore
?>

<script>
 
    // Javascript code for improved implementation
     
    // Function for printing all elements of []B
    // that are not divisible by any element of []A
    function printNonDivisible(A, B, n, m)
    {
        // Find maximum element in []B
        let maxB = 0;
        for (let i = 0; i < m; i++)
            if (B[i] > maxB)
                maxB = B[i];
 
        // Initialize all multiples as marked
        let mark = new Array(maxB + 1);
        for(let i = 0; i < maxB; i++)
            mark[i] = 0;
 
        // Marking the multiples of all the
        // elements of the array.
        for (let i = 0; i < n; i++)
            for (let x = A[i]; x <= maxB; x += A[i])
                mark[x]++;
 
        // Print not marked elements
        for (let i = 0; i < m; i++)
            if (mark[B[i]] == 0)
                document.write(B[i] + "</br>");
    }
     
    let A= [100, 200, 400, 100];
    let n = A.length;
    let B= [190, 200, 87, 600, 800];
    let m = B.length;
    printNonDivisible(A, B, n, m);
     
</script>

190
87

Complejidad de tiempo :- O(m + n*(max(B[]/min(A[]))) 
Espacio auxiliar :- O(n) + O(m) + O(max(B[])) 

Este artículo es una contribución de Sakshi Tiwari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.