Given an array arr[] consisting of positive integers and an integer K, the task is to find the minimum number of operations required to make the product of all elements of the array divisible by K where in one operation you can select any prime number and insert it into the array.
Examples:
Input: arr[] = {6, 7, 8, 9, 3}, K = 15
Output: 1
Explanation: The product of the array is 9072. Add 5 to the array now the product becomes 45360 which is exactly divisible by 15.Input: arr[] = {4, 8, 19, 23}, K = 66
Output: 2
Explanation: Insert 3 and 11 into the array and the product of the final array becomes divisible by 66. It is guaranteed that at least 2 operations are required.
Approach: To solve the problem follow the below idea and observations:
Observations:
- The elementary intuition suggests taking the product of all array elements and dividing it by K. Whatever the number obtained (say Y), we need to find the number of primes occurring in its prime factorization. But the issue is that the product of all elements may go beyond the maximum value of integer datatypes i.e. 1018.
- However, another noteworthy point is that we don’t need to calculate the product of the array as we are only concerned with the prime factorization of the number obtained upon the division of the array product by X.
This observation leads to the following approach:
If a number A divides another number B then the following shall always be true:
- All the prime factors of A should be present in prime factorization of B.
- For each prime factor of A, It’s number of occurrences in prime factorization of B should be greater than equal to it’s number of occurrences in prime factorization of A.
- The problem statement can be related to the above idea. K is equivalent to A and B is equivalent to the array product. In spite of calculating the product of all elements of the array, for each individual element of the array count the frequency (number of occurrences) of each prime factor occurring in its calculation.
- When a case happens such that the frequency of a prime number num is greater in K (say p) than in array product (say q) we need to insert num into the main array (p-q) times.
Follow the below-mentioned steps to solve the problem:
- Calculate the frequency of the prime factors of all elements of the main array arr[] and store it in a map mp1.
- In other words, mp1 stores the product of the whole array in the form of prime factors. Each key-value pair represents a prime factor of the array product with its frequency.
- Perform a similar calculation for the number K and store all prime factors and their number of occurrences in another map mp2.
- Now for each element of mp2 evaluate the prime numbers whose frequency is greater in mp2 as compared to mp1. Add the difference of frequencies to the answer.
- Return the answer
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to calculate prime factors// of a numbervector<int> prime_factors(int num){ // Vector to store all the // factors of num vector<int> res; while (num % 2 == 0) { res.push_back(2); num /= 2; } for (int i = 3; i * i <= num; i += 2) { while (num % i == 0) { res.push_back(i); num /= i; } } // If the number is prime greater // than 2 if (num > 1) { res.push_back(num); } return res;}// Function to find the required// number of operationsint solve(int arr[], int n, int X){ // Initialize a map to store the // number of occurences of each // prime factor unordered_map<int, int> mp1; vector<int> cnt; for (int i = 0; i < n; i++) { // Compute the prime factors // for each element cnt = prime_factors(arr[i]); for (int j = 0; j < cnt.size(); j++) { // Increment the count of prime // factors of each mp1[cnt[j]]++; } // Clear the vector for storing // factors of other elements cnt.clear(); } vector<int> res = prime_factors(X); unordered_map<int, int> mp2; // Store the prime factors of // X in another map for (int i = 0; i < res.size(); i++) { mp2[res[i]]++; } // Compare each corresponding entitiy // of mp2 with mp1. If there exists a // which occurs in more number of // times in mp2 than in mp1 then // increment the ans. int ans = 0; for (auto it = mp2.begin(); it != mp2.end(); ++it) { if (it->second > mp1[it->first]) { ans += (it->second - mp1[it->first]); } } return ans;}// Driver Codeint main(){ // TestCase int arr[] = { 6, 4, 3 }; int N = sizeof(arr) / sizeof(arr[0]); int X = 35; // TestCase2 int arr2[] = { 6, 7, 8, 9, 3 }; int M = sizeof(arr2) / sizeof(arr2[0]); int Y = 15; // TestCase3 int arr3[] = { 4, 8, 19, 23 }; int O = sizeof(arr3) / sizeof(arr3[0]); int Z = 66; // Function Call cout << solve(arr, N, X) << endl; cout << solve(arr2, M, Y) << endl; cout << solve(arr3, O, Z) << endl; return 0;} |
Java
//Java code for the above approachimport java.util.*;class GFG {// Function to calculate prime factors of a numberstatic Vector<Integer> prime_factors(int num){ // Vector to store all the factors of num Vector<Integer> res = new Vector<Integer>(); while (num % 2 == 0) { res.add(2); num /= 2; } for (int i = 3; i * i <= num; i += 2) { while (num % i == 0) { res.add(i); num /= i; } } // If the number is prime greater than 2 if (num > 1) { res.add(num); } return res;}// Function to find the required number of operationsstatic int solve(int arr[], int n, int X){ // Initialize a map to store the number of occurences of each prime factor HashMap<Integer, Integer> mp1 = new HashMap<Integer, Integer>(); Vector<Integer> cnt; for (int i = 0; i < n; i++) { // Compute the prime factors for each element cnt = prime_factors(arr[i]); for (int j = 0; j < cnt.size(); j++) { // Increment the count of prime factors of each mp1.put(cnt.get(j), mp1.getOrDefault(cnt.get(j), 0) + 1); } // Clear the vector for storing factors of other elements cnt.clear(); } Vector<Integer> res = prime_factors(X); HashMap<Integer, Integer> mp2 = new HashMap<Integer, Integer>(); // Store the prime factors of X in another map for (int i = 0; i < res.size(); i++) { mp2.put(res.get(i), mp2.getOrDefault(res.get(i), 0) + 1); } // Compare each corresponding entity of mp2 with mp1. If there exists a which // occurs in more number of times in mp2 than in mp1 then increment the ans. int ans = 0; for (Map.Entry<Integer, Integer> entry : mp2.entrySet()) { if (entry.getValue() > mp1.getOrDefault(entry.getKey(), 0)) { ans += (entry.getValue() - mp1.getOrDefault(entry.getKey(), 0)); } } return ans;}public static void main(String[] args){ // TestCase int arr[] = { 6, 4, 3 }; int N = arr.length; int X = 35; // TestCase2 int arr2[] = { 6, 7, 8, 9, 3 }; int M = arr2.length; int Y = 15; // TestCase3 int arr3[] = { 4, 8, 19, 23 }; int O = arr3.length; int Z = 66; // Function Call System.out.println(solve(arr,N,X)); System.out.println(solve(arr2,M,Y)); System.out.println(solve(arr3,O,Z)); }} |
Python3
from typing import List# Function to calculate prime factors of a numberdef prime_factors(num: int) -> List[int]: factors = [] # While the number is divisible by 2 while num % 2 == 0: factors.append(2) num = num // 2 # Iterate from 3 to sqrt(num) for i in range(3, int(num**0.5) + 1, 2): while num % i == 0: factors.append(i) num = num // i # If the number is prime greater than 2 if num > 2: factors.append(num) return factors# Function to find the required number of operationsdef solve(arr: List[int], n: int, X: int) -> int: # Initialize a map to store the number of occurences of each prime factor factors_count = {} for i in range(n): factors = prime_factors(arr[i]) for factor in factors: if factor in factors_count: # Increment the count of prime factors of each factors_count[factor] += 1 else: factors_count[factor] = 1 X_factors = prime_factors(X) X_factors_count = {} for factor in X_factors: if factor in X_factors_count: X_factors_count[factor] += 1 else: X_factors_count[factor] = 1 ans = 0 # Compare each corresponding entitiy #of mp2 with mp1. If there exists a # which occurs in more number of # times in mp2 than in mp1 then #increment the ans. for factor in X_factors_count: if factor not in factors_count or X_factors_count[factor] > factors_count[factor]: ans += X_factors_count[factor] - factors_count.get(factor, 0) return ans# Driver code#Test Case 1arr = [6, 4, 3]N = len(arr)X = 35#Test Case 2print(solve(arr,N,X))arr2 = [6, 7, 8, 9, 3]M = len(arr2)Y = 15#Test Case 3print(solve(arr2,M,Y))arr3 = [4,8,19,23]O = len(arr3)Z = 66print(solve(arr3,O,Z))# This code is contributed by lokeshpotta20. |
Javascript
// Function to calculate prime factors of a numberfunction primeFactors(num) { let factors = []; while (num % 2 === 0) { factors.push(2); num = num / 2; } for (let i = 3; i <= Math.sqrt(num); i += 2) { while (num % i === 0) { factors.push(i); num = num / i; } } if (num > 2) { factors.push(num); } return factors;}// Function to find the required number of operationsfunction solve(arr, n, X) { let factorsCount = {}; for (let i = 0; i < n; i++) { let factors = primeFactors(arr[i]); for (let factor of factors) { if (factorsCount[factor]) { factorsCount[factor]++; } else { factorsCount[factor] = 1; } } } let XFactors = primeFactors(X); let XFactorsCount = {}; for (let factor of XFactors) { if (XFactorsCount[factor]) { XFactorsCount[factor]++; } else { XFactorsCount[factor] = 1; } } let ans = 0; for (let factor in XFactorsCount) { if (!factorsCount[factor] || XFactorsCount[factor] > factorsCount[factor]) { ans += XFactorsCount[factor] - (factorsCount[factor] || 0); } } return ans;}// Driver code// Test Case 1let arr = [6, 4, 3];let N = arr.length;let X = 35;console.log(solve(arr, N, X));// Test Case 2let arr2 = [6, 7, 8, 9, 3];let M = arr2.length;let Y = 15;console.log(solve(arr2, M, Y));// Test Case 3let arr3 = [4, 8, 19, 23];let O = arr3.length;let Z = 66;console.log(solve(arr3, O, Z)); |
C#
using System;using System.Collections.Generic;using System.Linq;class MainClass { // Function to calculate prime factors // of a number public static List<int> prime_factors(int num) { // List to store all the // factors of num List<int> res = new List<int>(); while (num % 2 == 0) { res.Add(2); num /= 2; } for (int i = 3; i * i <= num; i += 2) { while (num % i == 0) { res.Add(i); num /= i; } } // If the number is prime greater // than 2 if (num > 1) { res.Add(num); } return res; } // Function to find the required // number of operations public static int solve(int[] arr, int n, int X) { // Initialize a dictionary to store the // number of occurences of each // prime factor Dictionary<int, int> mp1 = new Dictionary<int, int>(); List<int> cnt; for (int i = 0; i < n; i++) { // Compute the prime factors // for each element cnt = prime_factors(arr[i]); for (int j = 0; j < cnt.Count; j++) { // Increment the count of prime // factors of each if (mp1.ContainsKey(cnt[j])) { mp1[cnt[j]]++; } else { mp1.Add(cnt[j], 1); } } // Clear the list for storing // factors of other elements cnt.Clear(); } List<int> res = prime_factors(X); Dictionary<int, int> mp2 = new Dictionary<int, int>(); // Store the prime factors of // X in another dictionary for (int i = 0; i < res.Count; i++) { if (mp2.ContainsKey(res[i])) { mp2[res[i]]++; } else { mp2.Add(res[i], 1); } } // Compare each corresponding entitiy // of mp2 with mp1. If there exists a // which occurs in more number of // times in mp2 than in mp1 then // increment the ans. int ans = 0; foreach (var item in mp2) { if (item.Value > mp1[item.Key]) { ans += (item.Value - mp1[item.Key]); } } return ans; } public static void Main(string[] args) { // TestCase int[] arr = { 6, 4, 3 }; int N = arr.Length; int X = 35; // TestCase2 int[] arr2 = { 6, 7, 8, 9, 3 };int M = arr2.Length;int Y = 15; // TestCase3 int[] arr3 = { 4, 8, 19, 23 }; int O = arr3.Length; int Z = 66; // Function Call Console.WriteLine(solve(arr, N, X)); Console.WriteLine(solve(arr2, M, Y)); Console.WriteLine(solve(arr3, O, Z));} |
Output
2 1 2
Time Complexity : O(N*sqrt(N))
Auxiliary Space : O(N)
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!
Share your thoughts in the comments
