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., 1310 = 1013. 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 Nint 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 kvector<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 codeint 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 Nstatic 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 kstatic 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 codepublic 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 Ndef 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 kdef 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 codeif __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 Nstatic 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 kstatic 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 codepublic 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 Nfunction 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 kfunction 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 codedocument.write(largestPowerOfB(5, 2) + "<br>");document.write(largestPowerOfB(6, 9) + "<br>");// This code is contributed by ShubhamSingh10</script> |
3 1
Time Complexity : O(logN * logB)
Space Complexity : O(logB)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
