Check divisibility of product of elements of arr1 and arr2
Given two arrays arr1[] and arr2[], the task is to check if the product of elements of arr1 is divisible by the product of elements of arr2, print “1”, else print “0”.
Examples:
Input: arrayA = [20, 40, 5, 8] arrayB = [2, 16, 10, 50, 1]
Output: 1
Explanation: Product of elements of arrayA = 20 * 40 * 5 * 8 = 32000
Product of elements of arrayB = 2 * 16 * 10 * 50 * 1 = 16000
Since, 32000 is divisible by 16000, therefore output will be “1”Input: arrayA = [20, 40, 5, 8] arrayB = [2, 16, 10, 80, 3]
Output: 0
Explanation: Product of elements of arrayA = 20 * 4 * 5 * 8 = 32000
Product of elements of arrayB = 2 * 16 * 10 * 50 * 3 = 76800
Since, 32000 is not divisible by 76800, therefore output will be “0”
Approach: To solve the problem follow the below observations:
Observations:
- We can observe that each and every number can be represented in terms of prime factors. When we multiply two numbers, the powers of their prime factors adds up. When we divide two numbers, the powers of their prime factors subtracts.
- Now, we find the powers of prime factors of each number in arrayA and adds up their power. Now for each number in arrayB, we can subtract the power of prime factor from the powers we got in arrayA.
- If at anytime, the power becomes negative, it means multiplication of arrayB elements will have extra power of that prime factor and hence it can be concluded that it will always remain in denominator and therefore, the answer should be “0”.
- If power never becomes negative, then the answer is “1” because all the prime factors in denominator have been cancelled by prime factors in numerator.
Used Formula:
(f1 ^ c1) * (f2 ^ c2) * …
————————– = (f1 ^ (c1 – k1)) * (f2 ^ (c2 – k2)) * …
(f1 ^ k1) * (f2 ^ k2) * …
Follow the steps to solve the problem:
- Create a hash map say.
- For each element in arr1, find its prime factors and store the frequency of prime factors in the hash map.
- For each element in arr2, find its prime factors of it and subtract the frequency of the prime factor from the frequency stored in the hash map.
- If at any time, any frequency becomes negative, return 0.
- If the frequencies always remain positive, return 1.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; void primeFactors( int n, unordered_map< int , int >& mp, int val) { // Store the number of 2s that // divide n while (n % 2 == 0) { mp[2] += val; n = n / 2; } // n must be odd at this point. So we // can skip one element (Note i = i +2) for ( int i = 3; i * i <= n; i = i + 2) { // While i divides n, change // frequencey of factor i // and divide n while (n % i == 0) { mp[i] += val; n = n / i; } } // This condition is to handle the // case when n is a prime number // greater than 2 if (n > 2) mp[n] += val; } void checkDivisibility( int arrA[], int arrB[], int N1, int N2) { // Create empty unordered Hash Map unordered_map< int , int > mp; // Increase frequency of prime // factors for arrayA for ( int i = 0; i < N1; i++) { primeFactors(arrA[i], mp, +1); } // Decrease frequency of prime // factors for arrayB for ( int i = 0; i < N2; i++) { primeFactors(arrB[i], mp, -1); } // Check frequency of each prime // factor in hash_map for ( auto e : mp) { // If frequency of prime // factor is negative if (e.second < 0) { cout << "0\n" ; return ; } } // If no frequency is negative cout << "1\n" ; } // Drivers code int main() { int N1 = 4; int N2 = 5; // Given arrays example-1 int arrA[] = { 20, 40, 5, 8 }; int arrB[] = { 2, 16, 10, 50, 1 }; checkDivisibility(arrA, arrB, N1, N2); // Given arrays example-2 int arrC[] = { 20, 40, 5, 8 }; int arrD[] = { 2, 16, 10, 80, 3 }; checkDivisibility(arrC, arrD, N1, N2); return 0; } |
Java
import java.util.*; public class Main { public static void primeFactors( int n, Map<Integer, Integer> mp, int val) { // Store the number of 2s that // divide n while (n % 2 == 0 ) { mp.put( 2 , mp.getOrDefault( 2 , 0 ) + val); n = n / 2 ; } // n must be odd at this point. So we // can skip one element (Note i = i +2) for ( int i = 3 ; i * i <= n; i = i + 2 ) { // While i divides n, change // frequency of factor i // and divide n while (n % i == 0 ) { mp.put(i, mp.getOrDefault(i, 0 ) + val); n = n / i; } } // This condition is to handle the // case when n is a prime number // greater than 2 if (n > 2 ) mp.put(n, mp.getOrDefault(n, 0 ) + val); } public static void checkDivisibility( int arrA[], int arrB[], int N1, int N2) { // Create empty unordered Hash Map Map<Integer, Integer> mp = new HashMap<>(); // Increase frequency of prime // factors for arrayA for ( int i = 0 ; i < N1; i++) { primeFactors(arrA[i], mp, + 1 ); } // Decrease frequency of prime // factors for arrayB for ( int i = 0 ; i < N2; i++) { primeFactors(arrB[i], mp, - 1 ); } // Check frequency of each prime // factor in hash_map for (Map.Entry<Integer, Integer> e : mp.entrySet()) { // If frequency of prime // factor is negative if (e.getValue() < 0 ) { System.out.println( "0" ); return ; } } // If no frequency is negative System.out.println( "1" ); } // Driver's code public static void main(String[] args) { int N1 = 4 ; int N2 = 5 ; // Given arrays example-1 int arrA[] = { 20 , 40 , 5 , 8 }; int arrB[] = { 2 , 16 , 10 , 50 , 1 }; checkDivisibility(arrA, arrB, N1, N2); // Given arrays example-2 int arrC[] = { 20 , 40 , 5 , 8 }; int arrD[] = { 2 , 16 , 10 , 80 , 3 }; checkDivisibility(arrC, arrD, N1, N2); } } |
Python3
def primeFactors(n, hash_map, val): # Store the number of two's that divide n while n % 2 = = 0 : n / = 2 if 2 in hash_map: hash_map[ 2 ] + = val else : hash_map[ 2 ] = val # n must be odd at this point # so a skip of 2 ( i = i + 2) can be used i = 3 while i * i < = n: # while i divides n, change frequency of factor i and divide n while n % i = = 0 : if i in hash_map: hash_map[i] + = val else : hash_map[i] = val n = n / i i + = 2 # Condition if n is a prime # number greater than 2 if n > 2 : if n in hash_map: hash_map[n] + = val else : hash_map[n] = val return hash_map def checkDivisibility(arrA, arrB): # Create an empty hashmap / dictionary hash_map = {} # Increase frequency of prime factors for arrayA for ele in arrA: hash_map = primeFactors(ele, hash_map, + 1 ) # Decrease frequency of prime factors for arrayB for ele in arrB: hash_map = primeFactors(ele, hash_map, - 1 ) # check frequency of each prime factor in hash_map for value in hash_map.values(): # if frequency of prime factor is negative if value < 0 : print ( "0" ) return # If no frequency is negative print ( "1" ) # Given arrays example-1 arrA = [ 20 , 40 , 5 , 8 ] arrB = [ 2 , 16 , 10 , 50 , 1 ] checkDivisibility(arrA, arrB) # Given arrays example-2 arrC = [ 20 , 40 , 5 , 8 ] arrD = [ 2 , 16 , 10 , 80 , 3 ] checkDivisibility(arrC, arrD) |
C#
using System; using System.Collections.Generic; class GFG { static void primeFactors( int n, Dictionary< int , int > mp, int val) { // Store the number of 2s that // divide n while (n % 2 == 0) { if (mp.ContainsKey(2)) { mp[2] += val; } else { mp.Add(2, val); } n /= 2; } // n must be odd at this point. So we // can skip one element (Note i = i +2) for ( int i = 3; i * i <= n; i += 2) { // While i divides n, change // frequency of factor i // and divide n while (n % i == 0) { if (mp.ContainsKey(i)) { mp[i] += val; } else { mp.Add(i, val); } n /= i; } } // This condition is to handle the // case when n is a prime number // greater than 2 if (n > 2) { if (mp.ContainsKey(n)) { mp[n] += val; } else { mp.Add(n, val); } } } static void checkDivisibility( int [] arrA, int [] arrB, int N1, int N2) { // Create empty dictionary Dictionary< int , int > mp = new Dictionary< int , int >(); // Increase frequency of prime // factors for arrayA for ( int i = 0; i < N1; i++) { primeFactors(arrA[i], mp, +1); } // Decrease frequency of prime // factors for arrayB for ( int i = 0; i < N2; i++) { primeFactors(arrB[i], mp, -1); } // Check frequency of each prime // factor in dictionary foreach (KeyValuePair< int , int > e in mp) { // If frequency of prime // factor is negative if (e.Value < 0) { Console.WriteLine( "0" ); return ; } } // If no frequency is negative Console.WriteLine( "1" ); } // Drivers code static void Main() { int N1 = 4; int N2 = 5; // Given arrays example-1 int [] arrA = { 20, 40, 5, 8 }; int [] arrB = { 2, 16, 10, 50, 1 }; checkDivisibility(arrA, arrB, N1, N2); // Given arrays example-2 int [] arrC = { 20, 40, 5, 8 }; int [] arrD = { 2, 16, 10, 80, 3 }; checkDivisibility(arrC, arrD, N1, N2); return ; } } |
Javascript
// JavaScript code implementation: function primeFactors(n, hash_map, val) { // Store the number of 2s that divide n while (n % 2 === 0) { n /= 2; if (2 in hash_map) { hash_map[2] += val; } else { hash_map[2] = val; } } // n must be odd at this point. So we // can skip one element (Note i = i +2) let i = 3; while (i * i <= n) { // while i divides n, change frequency // of factor i and divide n while (n % i === 0) { if (i in hash_map) { hash_map[i] += val; } else { hash_map[i] = val; } n /= i; } i += 2; } // Condition if n is a prime number greater than 2 if (n > 2) { if (n in hash_map) { hash_map[n] += val; } else { hash_map[n] = val; } } return hash_map; } function checkDivisibility(arrA, arrB) { // Create an empty map let hash_map = {}; // Increase frequency of prime factors for arrayA for (let ele of arrA) { hash_map = primeFactors(ele, hash_map, 1); } // Decrease frequency of prime factors for arrayB for (let ele of arrB) { hash_map = primeFactors(ele, hash_map, -1); } // Check frequency of each prime factor in hash_map for (let value of Object.values(hash_map)) { // if frequency of prime factor is negative if (value < 0) { console.log( "0" ); return ; } } // If no frequency is negative console.log( "1" ); } // Given arrays example-1 const arrA = [20, 40, 5, 8]; const arrB = [2, 16, 10, 50, 1]; checkDivisibility(arrA, arrB); // Given arrays example-2 const arrC = [20, 40, 5, 8]; const arrD = [2, 16, 10, 80, 3]; checkDivisibility(arrC, arrD); |
1 0
Time Complexity: O(N * √N)
Auxiliary Space: O(N)