Given two arrays A[] and B[], write an efficient code to determine if every element of B[] is divisible by at least 1 element of A[]. Display those elements of B[], which are not divisible by any of the elements in A[].
Examples :
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[].
Method I (Naive Implementation):
- Iterate through every single element of B[].
- Check if it is divisible by at least 1 element of A[] or not. If not divisible by any, then print it.
Implementation:
C++
// C++ code for naive implementation#include<iostream>using namespace std;// Function for checking the condition// with 2 loopsvoid 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 codeint 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
// Java code for naive implementationimport java.io.*;public class GFG { // Function for checking the condition// with 2 loopsstatic 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
# Python3 code for naive implementationimport math as mt# Function for checking the condition# with 2 loopsdef 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 codeA = [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#
// C# code for naive implementationusing System;public class GFG { // Function for checking the // condition with 2 loopsstatic 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// PHP code for naive implementation// Function for checking // the condition with 2 loopsfunction 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?> |
Javascript
<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> |
Output
190 87
Time Complexity :- O(n*m)
Auxiliary Space :- O(1)
Method 2 (Efficient when elements in are small)
- Maintain an array mark[] to mark the multiples of the numbers in A[].
- Mark all the multiples of all the elements in A[], till a max of B[].
- Check if mark[B[i]] value for every element n in B[] is not 0 and print if not marked.
Implementation:
C++
// 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 functionint 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
// Java code for improved implementationimport 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 codestatic 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. |
Python3
# 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 Codeif __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#
// C# code for improved implementationusing System;class GFG{ // Function for printing all elements of []B// that are not divisible by any element of []Astatic 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 codestatic 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// 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?> |
Javascript
<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> |
Output
190 87
Time Complexity :- O(m + n*(max(B[]/min(A[])))
Auxiliary Space :- O(n) + O(m) + O(max(B[]))
This article is contributed by Sakshi Tiwari .If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
