Power of factorial - Naukri Code 360

Q: What is a factorial?

The factorial of a number id defined by:

Q: N! = N * (N - 1) * (N - 2) * … * 2 * 1

For example: 4! = 4 * 3 * 2 * 1 = 24.

Q: How to find the divisors of a factorial?

Steps to find the divisors of a factorial:

Q: First, find the factorial of the given number.Then, count the total number of divisors of the factorial.

List the total divisors of 12!.

Introduction:

We are given two numbers N and K; we need to find the largest power of K that divides N! (factorial of N). In other words, we need to find the power of the factorial divisor.

We should initially think about the instance of prime K. The unequivocal articulation for

N! = 1⋅ 2 ⋅ 3…( N − 1 ) ⋅ N

Note that each K-th component of the item is separable by K, for example, adds +1 to the appropriate response; the quantity of such elements is

Then, every K2-th component is detachable by K2, adding another +1 to the appropriate response (the main force of K, has effectively been included in the past section). The quantity of such components is

The final answer is :

The total is limited since just roughly the first components are not zeros. Hence, the runtime of this calculation is

Doesn't that sound confusing?

Let’s figure it out with the help of a hands-on example.

Let’s consider n = 5, k = 2. Value of 5! = 120 and the largest power of k that divides the factorial result i.e. largest power of 2 that divides 120 is 8 (23).

Source :Giphy

Approach for Power of factorial in C++:

The efficient approach is based on Legendre’s formula. The following steps are followed: While dealing with this problem to find the maximum power of N that divides M factorial (M!), N can be anything prime or composite. Thus, in this case,

First, the prime factors of a given number N are calculated.
Then calculate the highest power from all prime factors that divides M!.
Finally, we’ll calculate the prime factor with the lowest value of the highest power of N that divides M!.
In other words, return the minimum of all calculated powers.

$<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>E</mi><mi>x</mi><mi>a</mi><mi>m</mi><mi>p</mi><mi>l</mi><mi>e</mi><mo>:</mo><mspace linebreak="newline"/><mi>f</mi><mi>a</mi><mi>c</mi><mi>t</mi><mo>=</mo><mn>146</mn><mo> </mo><mo>,</mo><mi>n</mi><mo>=</mo><mn>15</mn><mspace linebreak="newline"/><mi>F</mi><mi>i</mi><mi>r</mi><mi>s</mi><mi>t</mi><mo> </mo><mi>f</mi><mi>i</mi><mi>n</mi><mi>d</mi><mo> </mo><mi>t</mi><mi>h</mi><mi>e</mi><mo> </mo><mi>p</mi><mi>r</mi><mi>i</mi><mi>m</mi><mi>e</mi><mo> </mo><mi>f</mi><mi>a</mi><mi>c</mi><mi>t</mi><mi>o</mi><mi>r</mi><mo> </mo><mi>o</mi><mi>f</mi><mo> </mo><mn>15</mn><mo> </mo><mi>t</mi><mi>h</mi><mi>a</mi><mi>t</mi><mo> </mo><mi>a</mi><mi>r</mi><mi>e</mi><mo> </mo><mn>3</mn><mo> </mo><mi>a</mi><mi>n</mi><mi>d</mi><mo> </mo><mn>5</mn><mo> </mo><mi>t</mi><mi>h</mi><mi>e</mi><mi>n</mi><mo> </mo><mi>f</mi><mi>i</mi><mi>r</mi><mi>s</mi><mi>t</mi><mo> </mo><mi>d</mi><mi>i</mi><mi>v</mi><mi>i</mi><mi>d</mi><mi>e</mi><mo> </mo><mi>w</mi><mi>i</mi><mi>t</mi><mi>h</mi><mo> </mo><mn>3</mn><mo> </mo><mi>a</mi><mi>n</mi><mi>d</mi><mo> </mo><mi>a</mi><mi>d</mi><mi>d</mi><mo>.</mo><mspace linebreak="newline"/><mi>A</mi><mi>p</mi><mi>p</mi><mi>l</mi><mi>y</mi><mi>i</mi><mi>n</mi><mi>g</mi><mo> </mo><mi>L</mi><mi>e</mi><mi>g</mi><mi>e</mi><mi>n</mi><mi>d</mi><mi>r</mi><mi>e</mi><mo>’</mo><mi>s</mi><mo> </mo><mi>f</mi><mi>o</mi><mi>r</mi><mi>m</mi><mi>u</mi><mi>l</mi><mi>a</mi><mo> </mo><mi>f</mi><mi>o</mi><mi>r</mi><mo> </mo><mi>p</mi><mi>r</mi><mi>i</mi><mi>m</mi><mi>e</mi><mo> </mo><mi>f</mi><mi>a</mi><mi>c</mi><mi>t</mi><mi>o</mi><mi>r</mi><mo> </mo><mn>3</mn><mo>.</mo><mspace linebreak="newline"/><mfenced><mfrac><mn>146</mn><mn>3</mn></mfrac></mfenced><mo>+</mo><mfenced><mfrac><mn>48</mn><mn>3</mn></mfrac></mfenced><mo>+</mo><mfenced><mfrac><mn>16</mn><mn>3</mn></mfrac></mfenced><mo>+</mo><mfenced><mfrac><mn>5</mn><mn>3</mn></mfrac></mfenced><mo>+</mo><mfenced><mfrac><mn>1</mn><mn>3</mn></mfrac></mfenced><mo>=</mo><mn>70</mn><mo>.</mo><mspace linebreak="newline"/><mi>o</mi><mi>r</mi><mo>,</mo><mo> </mo><mn>48</mn><mo>+</mo><mn>16</mn><mo>+</mo><mn>5</mn><mo>+</mo><mn>1</mn><mo>+</mo><mn>0</mn><mo>=</mo><mn>70</mn><mo>.</mo><mspace linebreak="newline"/></math>$

$<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="18px"><mrow><mi>N</mi><mi>o</mi><mi>w</mi><mo>,</mo><mo> </mo><mi>a</mi><mi>p</mi><mi>p</mi><mi>l</mi><mi>y</mi><mi>i</mi><mi>n</mi><mi>g</mi><mo> </mo><mi>L</mi><mi>e</mi><mi>g</mi><mi>e</mi><mi>n</mi><mi>d</mi><mi>r</mi><mi>e</mi><mo>'</mo><mi>s</mi><mo> </mo><mi>F</mi><mi>o</mi><mi>r</mi><mi>m</mi><mi>u</mi><mi>l</mi><mi>a</mi><mo> </mo><mi>f</mi><mi>o</mi><mi>r</mi><mo> </mo><mi>p</mi><mi>r</mi><mi>i</mi><mi>m</mi><mi>e</mi><mo> </mo><mi>f</mi><mi>a</mi><mi>c</mi><mi>t</mi><mi>o</mi><mi>r</mi><mo> </mo><mi>o</mi><mi>f</mi><mo> </mo><mn>5</mn><mspace linebreak="newline"/><mfrac><mn>146</mn><mn>5</mn></mfrac><mo>+</mo><mfrac><mn>29</mn><mn>5</mn></mfrac><mo>+</mo><mfrac><mn>5</mn><mn>5</mn></mfrac><mo>+</mo><mfrac><mn>1</mn><mn>5</mn></mfrac><mo>=</mo><mn>35</mn><mspace linebreak="newline"/><mn>29</mn><mo>+</mo><mn>5</mn><mo>+</mo><mn>1</mn><mo>+</mo><mn>0</mn><mo>=</mo><mn>35</mn><mspace linebreak="newline"/><mi>h</mi><mi>e</mi><mi>r</mi><mi>e</mi><mo>,</mo><mo> </mo><mn>35</mn><mo> </mo><mi>i</mi><mi>s</mi><mo> </mo><mi>m</mi><mi>a</mi><mi>x</mi><mi>i</mi><mi>m</mi><mi>u</mi><mi>m</mi><mo> </mo><mi>p</mi><mi>o</mi><mi>w</mi><mi>e</mi><mi>r</mi><mo> </mo><mi>o</mi><mi>f</mi><mo> </mo><mi>p</mi><mi>r</mi><mi>i</mi><mi>m</mi><mi>e</mi><mo> </mo><mi>n</mi><mi>u</mi><mi>m</mi><mi>b</mi><mi>e</mi><mi>r</mi><mo> </mo><mn>5</mn></mrow></mstyle></math>$

As the minimum of both the numbers(35 and 70) is 35. So, the output is 35.

// Efficient approach for power of factorial divisor
#include <bits/stdc++.h>
using namespace std;

/*
Function to find the maximum power
of number p, which can divide the
original (num) number
*/
int PowerPrime(int num, int p)
{
int res = 0;
while (num > 0) {
res += num / p;
num /= p;
}

return res;
}

/*
The function that returns the sum
for all factors of n
*/
int PowerComposite(int num, int k)
{
/*
Variable res stores minimum
power of prime factor that divides fact!
*/
int res = INT_MAX;

/*
Loop to traverse through all
prime factors
*/
for (int i = 2; i <= sqrt(k); i++) {

/*
Counter variable that counts
power of the prime number
*/
int count = 0;
while (k % i == 0) {
count++;
k = k / i;
}

if (count > 0) {

/*
Maximum power of each i that divides
fact!, then divide by count to handle
multiple occurrences of a prime number
*/
int curr_pow = PowerPrime(num, i) / count;
res = min(res, curr_pow);
}
}

/*
Condition that checks the case when
n is prime number greater than 2
*/
if (k >= 2) {
int curr_pow = PowerPrime(num, k);
res = min(res, curr_pow);
}
return res;
}

// Driver code
int main()
{
int fact = 146, n = 5;

// Calling the required function
cout<<"Power of factorial divisor is:"<<" ";
cout << PowerComposite(fact, n);
return 0;
}

Output:

Power of factorial divisor is: 35

Note: if multiple powers of prime factors are present in n then divide the ‘count’ variable to get the maximum value of the factor.

Time Complexity:

Here ‘N’ is the number for which we need to return the largest power of factorial of ‘fact’.

An additional loop is used to find the prime factors of number N. But we cannot directly multiply the complexity by sqrt(N) because ‘PowerPrime()’ is not directly dependent on sqrt(N) or N . ‘N’ will have the changing values with N = N / i and every time N changes, the value of sqrt(N) also changes.

Space Complexity: O(1)

The space complexity of this approach is O(1). As constant space is used.

Also see, Euclid GCD Algorithm

Frequently asked questions:

What is a factorial?

The factorial of a number id defined by:

N! = N * (N - 1) * (N - 2) * … * 2 * 1

For example: 4! = 4 * 3 * 2 * 1 = 24.

How to find the divisors of a factorial?

Steps to find the divisors of a factorial:

First, find the factorial of the given number.
Then, count the total number of divisors of the factorial.

List the total divisors of 12!.

The divisors of 12 are 1, 2, 3, 4, 6, 12.

Is 18 a divisor of 6 and why?

No, 18 is not a divisor of 6. Because a divisor is one that divides opponent numbers either completely or with a remainder. And 18 don’t divide 6.

Key Takeaways:

In this article, we learned how to find the power of factorial divisors, starting from brute force solution to an efficient approach, a discussion around its time complexity, and have gone through some hands-on examples. To get a grip on more such exciting problems, visit code studio.

Happy coding

~ Pradipta Choudhury

Finding Power of Factorial Divisor