Given two integers N and M, the task is to find the count of possible sequences a1, a2, … of length N such that the product of all the elements of the sequence is M.
Examples:
Input: N = 2, M = 6
Output: 4
Possible sequences are {1, 6}, {2, 3}, {3, 2} and {6, 1}
Input: N = 3, M = 24
Output: 30
Approach:
- Consider the prime factorisation of M as p1k1p2k2 …pzkz.
- For each prime factor, its exponent has to be distributed among N different groups because on multiplying those N terms, the exponents of the prime factors will add. This can be done using the formula explained here.
- For each prime factor, the number of ways of distributing its exponents in N sequences would be equal to
N + Ki -1CN-1 for every 1 ? i ? z. - Using Fundamental Principle of Multiplication, multiply the results of all the prime factors to get the answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the// value of ncr effectivelyint ncr(int n, int r){ // Initializing the result int res = 1; for (int i = 1; i <= r; i += 1) { // Multiply and divide simultaneously // to avoid overflow res *= (n - r + i); res /= i; } // Return the answer return res;}// Function to return the number of sequences// of length N such that their product is Mint NoofSequences(int N, int M){ // Hashmap to store the prime factors of M unordered_map<int, int> prime; // Calculate the prime factors of M for (int i = 2; i <= sqrt(M); i += 1) { // If i divides M it means it is a factor // Divide M by i till it could be // divided to store the exponent while (M % i == 0) { // Increase the exponent count prime[i] += 1; M /= i; } } // If the number is a prime number // greater than sqrt(M) if (M > 1) { prime[M] += 1; } // Initializing the ans int ans = 1; // Multiply the answer for every prime factor for (auto it : prime) { // it.second represents the // exponent of every prime factor ans *= (ncr(N + it.second - 1, N - 1)); } // Return the result return ans;}// Driver codeint main(){ int N = 2, M = 6; cout << NoofSequences(N, M); return 0;} |
Java
// Java implementation of the above approachimport java.util.HashMap;class neveropen { // Function to calculate the // value of ncr effectively public static int nCr(int n, int r) { // Initializing the result int res = 1; for (int i = 1; i <= r; i++) { // Multiply and divide simultaneously // to avoid overflow res *= (n - r + i); res /= i; } // Return the answer return res; } // Function to return the number of sequences // of length N such that their product is M public static int NoofSequences(int N, int M) { // Hashmap to store the prime factors of M HashMap<Integer, Integer> prime = new HashMap<>(); // Calculate the prime factors of M for (int i = 2; i <= Math.sqrt(M); i++) { // If i divides M it means it is a factor // Divide M by i till it could be // divided to store the exponent while (M % i == 0) { // Increase the exponent count if (prime.get(i) == null) prime.put(i, 1); else { int x = prime.get(i); prime.put(i, ++x); } M /= i; } } // If the number is a prime number // greater than sqrt(M) if (M > 1) { if (prime.get(M) != null) { int x = prime.get(M); prime.put(M, ++x); } else prime.put(M, 1); } // Initializing the ans int ans = 1; // Multiply the answer for every prime factor for (HashMap.Entry<Integer, Integer> entry : prime.entrySet()) { // entry.getValue() represents the // exponent of every prime factor ans *= (nCr(N + entry.getValue() - 1, N - 1)); } // Return the result return ans; } // Driver code public static void main(String[] args) { int N = 2, M = 6; System.out.println(NoofSequences(N, M)); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 implementation of the above approach# Function to calculate the# value of ncr effectivelydef ncr(n, r): # Initializing the result res = 1 for i in range(1,r+1): # Multiply and divide simultaneously # to avoid overflow res *= (n - r + i) res //= i # Return the answer return res# Function to return the number of sequences# of length N such that their product is Mdef NoofSequences(N, M): # Hashmap to store the prime factors of M prime={} # Calculate the prime factors of M for i in range(2,int(M**(.5))+1): # If i divides M it means it is a factor # Divide M by i till it could be # divided to store the exponent while (M % i == 0): # Increase the exponent count prime[i]= prime.get(i,0)+1 M //= i # If the number is a prime number # greater than sqrt(M) if (M > 1): prime[M] =prime.get(M,0) + 1 # Initializing the ans ans = 1 # Multiply the answer for every prime factor for it in prime: # it.second represents the # exponent of every prime factor ans *= (ncr(N + prime[it] - 1, N - 1)) # Return the result return ans# Driver codeN = 2M = 6print(NoofSequences(N, M))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; public class neveropen { // Function to calculate the // value of ncr effectively public static int nCr(int n, int r) { // Initializing the result int res = 1; for (int i = 1; i <= r; i++) { // Multiply and divide simultaneously // to avoid overflow res *= (n - r + i); res /= i; } // Return the answer return res; } // Function to return the number of sequences // of length N such that their product is M public static int NoofSequences(int N, int M) { // Hashmap to store the prime factors of M Dictionary<int,int>prime = new Dictionary<int,int>(); // Calculate the prime factors of M for (int i = 2; i <= Math.Sqrt(M); i++) { // If i divides M it means it is a factor // Divide M by i till it could be // divided to store the exponent while (M % i == 0) { // Increase the exponent count if (!prime.ContainsKey(i)) prime.Add(i, 1); else { int x = prime[i]; prime.Remove(i); prime.Add(i, ++x); } M /= i; } } // If the number is a prime number // greater than sqrt(M) if (M > 1) { if (prime.ContainsKey(M)) { int x = prime[M]; prime.Remove(M); prime.Add(M, ++x); } else prime.Add(M, 1); } // Initializing the ans int ans = 1; // Multiply the answer for every prime factor foreach(KeyValuePair<int, int> entry in prime) { // entry.getValue() represents the // exponent of every prime factor ans *= (nCr(N + entry.Value - 1, N - 1)); } // Return the result return ans; } // Driver code public static void Main(String[] args) { int N = 2, M = 6; Console.WriteLine(NoofSequences(N, M)); }}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of the above approach // Function to calculate the // value of ncr effectively function nCr(n,r) { // Initializing the result let res = 1; for (let i = 1; i <= r; i++) { // Multiply and divide simultaneously // to avoid overflow res *= (n - r + i); res =Math.floor(res/ i); } // Return the answer return res; } // Function to return the number of sequences // of length N such that their product is M function NoofSequences(N,M) { // Hashmap to store the prime factors of M let prime = new Map(); // Calculate the prime factors of M for (let i = 2; i <= Math.sqrt(M); i++) { // If i divides M it means it is a factor // Divide M by i till it could be // divided to store the exponent while (M % i == 0) { // Increase the exponent count if (prime.get(i) == null) prime.set(i, 1); else { let x = prime.get(i); prime.set(i, ++x); } M = Math.floor(M/i); } } // If the number is a prime number // greater than sqrt(M) if (M > 1) { if (prime.get(M) != null) { let x = prime.get(M); prime.set(M, ++x); } else prime.set(M, 1); } // Initializing the ans let ans = 1; // Multiply the answer for every prime factor for (let [key, value] of prime.entries()) { // entry.getValue() represents the // exponent of every prime factor ans *= (nCr(N + value - 1, N - 1)); } // Return the result return ans; } // Driver code let N = 2, M = 6; document.write(NoofSequences(N, M));// This code is contributed by patel2127</script> |
Output:
4
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!
