Given an integer array arr[] of length N and an integer K, the task is to count the number of possible arrays of length K such that the product of all elements of that array is equal to the product of all elements of the given array arr[]. Since the answer can be very large, return the answer modulo 109 + 7. Examples:
Input: arr[] = {2, 3}, K = 3 Output: 9 The product of the elements of the array is 2 * 3 = 6. And there are 9 such arrays of length 3 possible, product of whose elements is 6, {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}, {1, 1, 6}, {1, 6, 1} and {6, 1, 1}. Input: arr[] = {1, 3, 5, 2}, K = 3 Output: 27
Prerequisites: Prime Factorization, Compute nCr % p Approach: Let the product of all the elements of arr[] be X. X can be represented by it’s prime factorization, i.e., X = p1c1*p2c2*…*prcr where pi are primes and ci are some non-negative coefficients. Let the K sized array be B[]. Instead of finding actual integers for B[], find the prime factorization for each Bi. The prime factorization of any number from B[] can’t have any prime except the primes which are factor of X because X % Bi should be equal to zero.
Thus, Bi = p1c1i * p2c2i * … * prcri with cij >= 0. And so, B1 * B2 * … Bk = p1(c11 + c12 + … + c1k) * p2(c21 + c22 + … + c2k) * … * pr(cr1 + cr2 + … + crk). Equating B1 * B2 * … Bk = X = p1c1*p2c2*…*prcr, we get r equations. c11 + c12 + … + c1k = c1 c21 + c22 + … + c2k = c2 . . . cr1 + cr2 + … + crk = cr where cij >= 0
Answer to ith equation is equal to the number of ways of distributing ci identical balls in K distinguishable boxes and so it is ci + K – 1 C K – 1. All the equations are independent, and so final answer = multiplication of answer to each equation. Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define ll long long#define MAXN (ll)(1e5 + 1)#define mod (ll)(1e9 + 7)// To store the smallest prime factor// for every numberll spf[MAXN];// Initialize map to store// count of prime factorsmap<ll, ll> cnt;// Function to calculate SPF(Smallest Prime Factor)// for every number till MAXNvoid sieve(){ spf[1] = 1; for (int i = 2; i < MAXN; i++) // Marking smallest prime factor for every // number to be itself spf[i] = i; // Separately marking spf for every even // number as 2 for (int i = 4; i < MAXN; i += 2) spf[i] = 2; for (int i = 3; i * i < MAXN; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all numbers divisible by i for (int j = i * i; j < MAXN; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } }}// Function to factorize using spf// and store in cntvoid factorize(ll f){ while (f > 1) { ll x = spf[f]; while (f % x == 0) { cnt[x]++; f /= x; } }}// Function to return n! % pll factorial(ll n, ll p){ // Initialize result ll res = 1; for (int i = 2; i <= n; i++) res = (res * i) % p; return res;}// Iterative Function to calculate (x^y)%p// in O(log y)ll power(ll x, ll y, ll p){ // Initialize result ll res = 1; // Update x if it is >= p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now // y = y/2 y = y >> 1; x = (x * x) % p; } return res;}// Function that returns n^(-1) mod pll modInverse(ll n, ll p){ return power(n, p - 2, p);}// Function that returns nCr % p// using Fermat's little theoremll nCrModP(ll n, ll r, ll p){ // Base case if (r == 0) return 1; // Fill factorial array so that we // can find all factorial of r, n // and n - r ll fac[n + 1]; fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p; return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;}// Function to return the count the number of possible// arrays mod P of length K such that the product of all// elements of that array is equal to the product of// all elements of the given array of length Nll countArrays(ll arr[], ll N, ll K, ll P){ // Initialize result ll res = 1; // Call sieve to get spf sieve(); for (int i = 0; i < N; i++) { // Factorize arr[i], count and // store its factors in cnt factorize(arr[i]); } for (auto i : cnt) { int ci = i.second; res = (res * nCrModP(ci + K - 1, K - 1, P)) % P; } return res;}// Driver codeint main(){ ll arr[] = { 1, 3, 5, 2 }, K = 3; ll N = sizeof(arr) / sizeof(arr[0]); cout << countArrays(arr, N, K, mod); return 0;} |
Java
// Java implementation of the approach import java.util.HashMap;class GFG { static long MAXN = 100001L, mod = 1000000007L; // To store the smallest prime factor // for every number static long[] spf = new long[(int) MAXN]; // Initialize map to store // count of prime factors static HashMap<Long, Long> cnt = new HashMap<>(); // Function to calculate SPF(Smallest Prime Factor) // for every number till MAXN public static void sieve() { spf[1] = 1; for (int i = 2; i < MAXN; i++) // Marking smallest prime factor for every // number to be itself spf[i] = i; // Separately marking spf for every even // number as 2 for (int i = 4; i < MAXN; i += 2) spf[i] = 2; for (int i = 3; i * i < MAXN; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all numbers divisible by i for (int j = i * i; j < MAXN; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } } } // Function to factorize using spf // and store in cnt public static void factorize(long f) { while (f > 1) { long x = spf[(int) f]; while (f % x == 0) { if (cnt.containsKey(x)) { long z = cnt.get(x); cnt.put(x, ++z); } else cnt.put(x, (long) 1); f /= x; } } } // Function to return n! % p public static long factorial(long n, long p) { // Initialize result long res = 1; for (long i = 2; i <= n; i++) res = (res * i) % p; return res; } // Iterative Function to calculate (x^y)%p // in O(log y) public static long power(long x, long y, long p) { // Initialize result long res = 1; // Update x if it is >= p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) res = (res * x) % p; // y must be even now // y = y/2 y = y >> 1; x = (x * x) % p; } return res; } // Function that returns n^(-1) mod p public static long modInverse(long n, long p) { return power(n, p - 2, p); } // Function that returns nCr % p // using Fermat's little theorem public static long nCrModP(long n, long r, long p) { // Base case if (r == 0) return 1; // Fill factorial array so that we // can find all factorial of r, n // and n - r long[] fac = new long[(int) n + 1]; fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p; return (fac[(int) n] * modInverse(fac[(int) r], p) % p * modInverse(fac[(int) (n - r)], p) % p) % p; } // Function to return the count the number of possible // arrays mod P of length K such that the product of all // elements of that array is equal to the product of // all elements of the given array of length N public static long countArrays(long[] arr, long N, long K, long P) { // Initialize result long res = 1; // Call sieve to get spf sieve(); for (int i = 0; i < N; i++) { // Factorize arr[i], count and // store its factors in cnt factorize(arr[i]); } for (HashMap.Entry<Long, Long> entry : cnt.entrySet()) { long ci = entry.getValue(); res = (res * nCrModP(ci + K - 1, K - 1, P)) % P; } return res; } // Driver code public static void main(String[] args) { long[] arr = { 1, 3, 5, 2 }; long K = 3; long N = arr.length; System.out.println(countArrays(arr, N, K, mod)); }}// This code is contributed by// sanjeev2552 |
Python3
# Python 3 implementation of the approachfrom math import sqrtMAXN = 100001mod = 1000000007# To store the smallest prime factor# for every numberspf = [0 for i in range(MAXN)]# Initialize map to store# count of prime factorscnt = {i:0 for i in range(10)}# Function to calculate SPF(Smallest Prime Factor)# for every number till MAXNdef sieve(): spf[1] = 1 for i in range(2,MAXN): # Marking smallest prime factor for every # number to be itself spf[i] = i # Separately marking spf for every even # number as 2 for i in range(4,MAXN,2): spf[i] = 2 for i in range(3,int(sqrt(MAXN))+1,1): # Checking if i is prime if (spf[i] == i): # Marking SPF for all numbers divisible by i for j in range(i * i,MAXN,i): # Marking spf[j] if it is not # previously marked if (spf[j] == j): spf[j] = i# Function to factorize using spf# and store in cntdef factorize(f): while (f > 1): x = spf[f] while (f % x == 0): cnt[x] += 1 f = int(f/x)# Function to return n! % pdef factorial(n,p): #Initialize result res = 1 for i in range(2,n+1,1): res = (res * i) % p return res# Iterative Function to calculate (x^y)%p# in O(log y)def power(x, y, p): # Initialize result res = 1 # Update x if it is >= p x = x % p while (y > 0): # If y is odd, multiply x with result if (y & 1): res = (res * x) % p # y must be even now # y = y/2 y = y >> 1 x = (x * x) % p return res# Function that returns n^(-1) mod pdef modInverse(n,p): return power(n, p - 2, p)# Function that returns nCr % p# using Fermat's little theoremdef nCrModP(n,r,p): # Base case if (r == 0): return 1 # Fill factorial array so that we # can find all factorial of r, n # and n - r fac = [0 for i in range(n+1)] fac[0] = 1 for i in range(1,n+1,1): fac[i] = fac[i - 1] * i % p return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p)% p# Function to return the count the number of possible# arrays mod P of length K such that the product of all# elements of that array is equal to the product of# all elements of the given array of length Ndef countArrays(arr,N,K,P): # Initialize result res = 1 # Call sieve to get spf sieve() for i in range(N): # Factorize arr[i], count and # store its factors in cnt factorize(arr[i]) for key,value in cnt.items(): ci = value res = (res * nCrModP(ci + K - 1, K - 1, P)) % P return res# Driver codeif __name__ == '__main__': arr = [1, 3, 5, 2] K = 3 N = len(arr) print(countArrays(arr, N, K, mod))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approach using System;using System.Collections.Generic; class GFG { static long MAXN = 100001L, mod = 1000000007L; // To store the smallest prime factor // for every number static long[] spf = new long[(int) MAXN]; // Initialize map to store // count of prime factors static Dictionary<long, long> cnt = new Dictionary<long, long>(); // Function to calculate SPF(Smallest Prime Factor) // for every number till MAXN public static void sieve() { spf[1] = 1; for (int i = 2; i < MAXN; i++) // Marking smallest prime factor for every // number to be itself spf[i] = i; // Separately marking spf for every even // number as 2 for (int i = 4; i < MAXN; i += 2) spf[i] = 2; for (int i = 3; i * i < MAXN; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all numbers divisible by i for (int j = i * i; j < MAXN; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } } } // Function to factorize using spf // and store in cnt public static void factorize(long f) { while (f > 1) { long x = spf[(int) f]; while (f % x == 0) { if (cnt.ContainsKey(x)) { long z = cnt[x]; cnt[x] = ++z; } else cnt.Add(x, (long) 1); f /= x; } } } // Function to return n! % p public static long factorial(long n, long p) { // Initialize result long res = 1; for (long i = 2; i <= n; i++) res = (res * i) % p; return res; } // Iterative Function to calculate (x^y)%p // in O(log y) public static long power(long x, long y, long p) { // Initialize result long res = 1; // Update x if it is >= p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) res = (res * x) % p; // y must be even now // y = y/2 y = y >> 1; x = (x * x) % p; } return res; } // Function that returns n^(-1) mod p public static long modInverse(long n, long p) { return power(n, p - 2, p); } // Function that returns nCr % p // using Fermat's little theorem public static long nCrModP(long n, long r, long p) { // Base case if (r == 0) return 1; // Fill factorial array so that we // can find all factorial of r, n // and n - r long[] fac = new long[(int) n + 1]; fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p; return (fac[(int) n] * modInverse(fac[(int) r], p) % p * modInverse(fac[(int) (n - r)], p) % p) % p; } // Function to return the count the number of possible // arrays mod P of length K such that the product of all // elements of that array is equal to the product of // all elements of the given array of length N public static long countArrays(long[] arr, long N, long K, long P) { // Initialize result long res = 1; // Call sieve to get spf sieve(); for (int i = 0; i < N; i++) { // Factorize arr[i], count and // store its factors in cnt factorize(arr[i]); } foreach(KeyValuePair<long, long> entry in cnt) { long ci = entry.Value; res = (res * nCrModP(ci + K - 1, K - 1, P)) % P; } return res; } // Driver code public static void Main(String[] args) { long[] arr = { 1, 3, 5, 2 }; long K = 3; long N = arr.Length; Console.WriteLine(countArrays(arr, N, K, mod)); }}// This code is contributed by PrinciRaj1992 |
Javascript
// JavaScript implementation of the approachlet MAXN = 100001nlet mod = 1000000007n// To store the smallest prime factor// for every numberlet spf = new Array(MAXN).fill(0n)// Initialize map to store// count of prime factorslet cnt = {} for (var i = 0n; i < 10; i++) cnt[i] = 0n;// Function to calculate SPF(Smallest Prime Factor)// for every number till MAXNfunction sieve(){ spf[1] = 1n for (var i = 2n; i < MAXN; i++) // Marking smallest prime factor for every // number to be itself spf[i] = i // Separately marking spf for every even // number as 2 for (var i = 4n; i < MAXN; i += 2n) spf[i] = 2n for (var i = 3n; i * i < MAXN; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all numbers divisible by i for (var j = i * i; j < MAXN; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i } }}// Function to factorize using spf// and store in cntfunction factorize(f){ while (f > 1n) { let x = spf[f] while (f % x == 0n) { cnt[x] += 1n f = (f - (f % x)) / x } }}// Function to return n! % pfunction factorial(n,p){ //Initialize result let res = 1n for (var i = 2n; i <= n; i++) res = (res * i) % p return res}// Iterative Function to calculate (x^y)%p// in O(log y)function power(x, y, p){ // Initialize result let res = 1n // Update x if it is >= p x = x % p while (y > 0n) { // If y is odd, multiply x with result if (y & 1n) res = (res * x) % p // y must be even now // y = y/2 y = y >> 1n x = (x * x) % p } return res}// Function that returns n^(-1) mod pfunction modInverse(n,p){ return power(n, p - 2n, p)}// Function that returns nCr % p// using Fermat's little theoremfunction nCrModP(n,r,p){ // Base case if (r == 0n) return 1n // Fill factorial array so that we // can find all factorial of r, n // and n - r let fac = new Array(n + 1n).fill(0n) fac[0] = 1n for (var i = 1n; i <= n; i++) fac[i] = fac[i - 1n] * i % p return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p)% p}// Function to return the count the number of possible// arrays mod P of length K such that the product of all// elements of that array is equal to the product of// all elements of the given array of length Nfunction countArrays(arr,N,K,P){ // Initialize result let res = 1n // Call sieve to get spf sieve() for (var i = 0n; i < N; i++) // Factorize arr[i], count and // store its factors in cnt factorize(arr[i]) for ( const [key,value] of Object.entries(cnt)) { let ci = value res = (res * nCrModP(ci + K - 1n, K - 1n, P)) % P } return res}// Driver codelet arr = [1n, 3n, 5n, 2n]let K = 3nlet N = arr.lengthconsole.log(countArrays(arr, N, K, mod))// This code is contributed by// phasing17 |
Output:
27
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!
