Number of trailing zeroes in base B representation of N!

0 0 7 minutes read

Given two positive integers B and N. The task is to find the number of trailing zeroes in b-ary (base B) representation of N! (factorial of N)
Examples:

Input: N = 5, B = 2
Output: 3
5! = 120 which is represented as 1111000 in base 2. 

Input: N = 6, B = 9
Output: 1

A naive solution is to find the factorial of the given number and convert it into given base B. Then, count the number of trailing zeroes but that would be a costly operation. Also, it will not be easy to find the factorial of large numbers and store it in integer.
Efficient Approach: Suppose, the base is 10 i.e., decimal then we’ll have to calculate the highest power of 10 that divides N! using Legendre’s formula. Thus, number B is represented as 10 when converted into base B. Let’s say base B = 13, then 13 in base 13 will be represented as 10, i.e., 13₁₀ = 10₁₃. Hence, problem reduces to finding the highest power of B in N!. (Largest power of k in n!)

Steps to solve the problem:

1. Function findPowerOfP takes two integer inputs N and p and returns an integer value count.

*Initialize a variable count to 0 and another variable r to p.

*While r is less than or equal to N, do the following steps:

*Calculate floor(N/r) and add it to count.

*Multiply r with p.

*Return count.

2. Function primeFactorsofB takes an integer input B and returns a vector of pairs of integers.

*Initialize an empty vector ans.

*Iterate from i=2 until B is not equal to 1, do the following:

*If B is divisible by i, initialize a variable count to 0 and do the following:

*While B is divisible by i, divide B by i and increment count.

*Add a pair of i and count to ans.

*Return ans.

3. Function largestPowerOfB takes two integer inputs N and B and returns an integer value.

*Initialize a vector of pairs vec and assign it the value returned by the function primeFactorsofB with input B.

*Initialize a variable ans to INT_MAX.

*Iterate from i=0 until i is less than the size of vec, do the following:

*Calculate the minimum of ans and the result of findPowerOfP with inputs N and vec[i].first divided by vec[i].second.

*Return ans.

Below is the implementation of the above approach.

C++

// CPP program to find the number of trailing
// zeroes in base B representation of N!
#include <bits/stdc++.h>
using namespace std;
 
// To find the power of a prime p in
// factorial N
int findPowerOfP(int N, int p)
{
    int count = 0;
    int r = p;
    while (r <= N) {
 
        // calculating floor(n/r)
        // and adding to the count
        count += (N / r);
 
        // increasing the power of p
        // from 1 to 2 to 3 and so on
        r = r * p;
    }
    return count;
}
 
// returns all the prime factors of k
vector<pair<int, int> > primeFactorsofB(int B)
{
    // vector to store all the prime factors
    // along with their number of occurrence
    // in factorization of B
    vector<pair<int, int> > ans;
 
    for (int i = 2; B != 1; i++) {
        if (B % i == 0) {
            int count = 0;
            while (B % i == 0) {
                B = B / i;
                count++;
            }
 
            ans.push_back(make_pair(i, count));
        }
    }
    return ans;
}
 
// Returns largest power of B that
// divides N!
int largestPowerOfB(int N, int B)
{
    vector<pair<int, int> > vec;
    vec = primeFactorsofB(B);
    int ans = INT_MAX;
    for (int i = 0; i < vec.size(); i++)
 
        // calculating minimum power of all
        // the prime factors of B
        ans = min(ans, findPowerOfP(N,
                                    vec[i].first)
                           / vec[i].second);
 
    return ans;
}
 
// Driver code
int main()
{
    cout << largestPowerOfB(5, 2) << endl;
    cout << largestPowerOfB(6, 9) << endl;
    return 0;
}

Java

// Java program to find the number of trailing
// zeroes in base B representation of N!
import java.util.*;
class GFG 
{
static class pair
{ 
    int first, second; 
    public pair(int first, int second) 
    { 
        this.first = first; 
        this.second = second; 
    } 
} 
 
// To find the power of a prime p in
// factorial N
static int findPowerOfP(int N, int p)
{
    int count = 0;
    int r = p;
    while (r <= N)
    {
 
        // calculating floor(n/r)
        // and adding to the count
        count += (N / r);
 
        // increasing the power of p
        // from 1 to 2 to 3 and so on
        r = r * p;
    }
    return count;
}
 
// returns all the prime factors of k
static Vector<pair> primeFactorsofB(int B)
{
    // vector to store all the prime factors
    // along with their number of occurrence
    // in factorization of B
    Vector<pair> ans = new Vector<pair>();
 
    for (int i = 2; B != 1; i++)
    {
        if (B % i == 0) 
        {
            int count = 0;
            while (B % i == 0)
            {
                B = B / i;
                count++;
            }
 
            ans.add(new pair(i, count));
        }
    }
    return ans;
}
 
// Returns largest power of B that
// divides N!
static int largestPowerOfB(int N, int B)
{
    Vector<pair> vec = new Vector<pair>();
    vec = primeFactorsofB(B);
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < vec.size(); i++)
 
        // calculating minimum power of all
        // the prime factors of B
        ans = Math.min(ans, findPowerOfP(
                       N, vec.get(i).first) / 
                          vec.get(i).second);
 
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    System.out.println(largestPowerOfB(5, 2));
    System.out.println(largestPowerOfB(6, 9));
}
}
 
// This code is contributed by Princi Singh

Python3

# Python 3 program to find the number of 
# trailing zeroes in base B representation of N!
import sys
 
# To find the power of a prime 
# p in factorial N
def findPowerOfP(N, p):
    count = 0
    r = p
    while (r <= N):
         
        # calculating floor(n/r)
        # and adding to the count
        count += int(N / r)
 
        # increasing the power of p
        # from 1 to 2 to 3 and so on
        r = r * p 
     
    return count
 
# returns all the prime factors of k
def primeFactorsofB(B):
     
    # vector to store all the prime factors
    # along with their number of occurrence
    # in factorization of B'
    ans = []
    i = 2
 
    while(B!= 1):
        if (B % i == 0):
            count = 0
            while (B % i == 0):
                 
                B = int(B / i)
                count += 1
 
            ans.append((i, count))
 
        i += 1
     
    return ans
 
# Returns largest power of B that
# divides N!
def largestPowerOfB(N, B):
    vec = []
    vec = primeFactorsofB(B)
    ans = sys.maxsize
     
    # calculating minimum power of all
    # the prime factors of B
    ans = min(ans, int(findPowerOfP(N, vec[0][0]) /
                                       vec[0][1]))
 
    return ans
 
# Driver code
if __name__ == '__main__':
    print(largestPowerOfB(5, 2))
    print(largestPowerOfB(6, 9))
     
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to find the number of trailing
// zeroes in base B representation of N!
using System;
using System.Collections.Generic; 
 
class GFG 
{
public class pair
{ 
    public int first, second; 
    public pair(int first, int second) 
    { 
        this.first = first; 
        this.second = second; 
    } 
} 
 
// To find the power of a prime p in
// factorial N
static int findPowerOfP(int N, int p)
{
    int count = 0;
    int r = p;
    while (r <= N)
    {
 
        // calculating floor(n/r)
        // and adding to the count
        count += (N / r);
 
        // increasing the power of p
        // from 1 to 2 to 3 and so on
        r = r * p;
    }
    return count;
}
 
// returns all the prime factors of k
static List<pair> primeFactorsofB(int B)
{
    // vector to store all the prime factors
    // along with their number of occurrence
    // in factorization of B
    List<pair> ans = new List<pair>();
 
    for (int i = 2; B != 1; i++)
    {
        if (B % i == 0) 
        {
            int count = 0;
            while (B % i == 0)
            {
                B = B / i;
                count++;
            }
 
            ans.Add(new pair(i, count));
        }
    }
    return ans;
}
 
// Returns largest power of B that
// divides N!
static int largestPowerOfB(int N, int B)
{
    List<pair> vec = new List<pair>();
    vec = primeFactorsofB(B);
    int ans = int.MaxValue;
    for (int i = 0; i < vec.Count; i++)
 
        // calculating minimum power of all
        // the prime factors of B
        ans = Math.Min(ans, findPowerOfP(
                       N, vec[i].first) / 
                          vec[i].second);
 
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    Console.WriteLine(largestPowerOfB(5, 2));
    Console.WriteLine(largestPowerOfB(6, 9));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to find the number of trailing
// zeroes in base B representation of N!
 
// To find the power of a prime p in
// factorial N
function findPowerOfP(N, p)
{
    var count = 0;
    var r = p;
    while (r <= N) {
 
        // calculating floor(n/r)
        // and adding to the count
        count += (N / r);
 
        // increasing the power of p
        // from 1 to 2 to 3 and so on
        r = r * p;
    }
    return count;
}
 
// returns all the prime factors of k
function primeFactorsofB(B)
{
    // vector to store all the prime factors
    // along with their number of occurrence
    // in factorization of B
    var ans = [];
 
    for (var i = 2; B != 1; i++) {
        if (B % i == 0) {
            var count = 0;
            while (B % i == 0) {
                B = B / i;
                count++;
            }
 
            ans.push([i, count]);
        }
    }
    return ans;
}
 
// Returns largest power of B that
// divides N!
function largestPowerOfB(N, B)
{
    var vec =[];
    vec = primeFactorsofB(B);
    var ans = Number.MAX_VALUE;
    for (var i = 0; i < vec.length; i++)
 
        // calculating minimum power of all
        // the prime factors of B
        ans = Math.min(ans, Math.floor(findPowerOfP(N, 
        vec[i][0]) / vec[i][1]));
 
    return ans;
}
 
// Driver code
document.write(largestPowerOfB(5, 2) + "<br>");
document.write(largestPowerOfB(6, 9) + "<br>");
 
// This code is contributed by ShubhamSingh10
 
</script>

Output:

3
1

Time Complexity : O(logN * logB)

Space Complexity : O(logB)

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 zambiatek!