Given an integer n and base B, the task is to find the length of n! in base B.
Examples:
Input: n = 4, b = 10
Output: 2
Explanation: 4! = 24, hence number of digits is 2Input: n = 4, b = 16
Output: 2
Explanation: 4! = 18 in base 16, hence number of digits is 2
Brute Force Approach:
The brute force approach to solve this problem would involve finding the value of n! in base B and then finding the number of digits in that value by repeatedly dividing the value by B until it becomes 0.
- Find the value of n! in base B using the standard factorial algorithm but with each intermediate result being converted to base B.
- Initialize a variable count to 0.
- Divide the value of n! in base B by B until it becomes 0, incrementing count each time.
- Return count as the answer.
Below is implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to convert a number to a given basestring toBase(long long num, int base){ string digits = "0123456789ABCDEF"; string res = ""; while (num > 0) { res = digits[num % base] + res; num /= base; } return res;}// Function to find the length of n! in base Blong long findDigits(int n, int b){ long long fact = 1; for (int i = 2; i <= n; i++) fact *= i; string fact_base_b = toBase(fact, b); long long count = 0; while (fact > 0) { count++; fact /= b; } return count;}// Driver codeint main(){ cout << findDigits(4, 16) << endl; cout << findDigits(5, 8) << endl; cout << findDigits(12, 16) << endl; cout << findDigits(19, 13) << endl; return 0;} |
Java
import java.util.*;public class Main { // Function to convert a number to a given base public static String toBase(long num, int base) { String digits = "0123456789ABCDEF"; String res = ""; while (num > 0) { res = digits.charAt((int) (num % base)) + res; num /= base; } return res; } // Function to find the length of n! in base B public static long findDigits(int n, int b) { long fact = 1; for (int i = 2; i <= n; i++) { fact *= i; } String fact_base_b = toBase(fact, b); long count = 0; while (fact > 0) { count++; fact /= b; } return count; } // Driver code public static void main(String[] args) { System.out.println(findDigits(4, 16)); System.out.println(findDigits(5, 8)); System.out.println(findDigits(12, 16)); System.out.println(findDigits(19, 13)); }} |
Python3
# code# Function to convert a number to a given basedef toBase(num, base): digits = "0123456789ABCDEF" # digits used in different bases res = "" while num > 0: res = digits[num % base] + res # add the digit to the result string num //= base # integer division by the base return res# Function to find the length of n! in base Bdef findDigits(n, b): fact = 1 for i in range(2, n + 1): # calculate the factorial of n fact *= i fact_base_b = toBase(fact, b) # convert factorial to base b count = 0 while fact > 0: count += 1 # increment count for each digit fact //= b # integer division by the base return count# Driver codeprint(findDigits(4, 16)) print(findDigits(5, 8)) print(findDigits(12, 16)) print(findDigits(19, 13)) |
C#
using System;namespace ConsoleApp {class Program { // Function to convert a number to a given base static string ToBase(long num, int baseNum) { string digits = "0123456789ABCDEF"; string res = ""; while (num > 0) { res = digits[(int)(num % baseNum)] + res; num /= baseNum; } return res; } // Function to find the length of n! in base B static long FindDigits(int n, int b) { long fact = 1; for (int i = 2; i <= n; i++) fact *= i; string fact_base_b = ToBase(fact, b); long count = 0; while (fact > 0) { count++; fact /= b; } return count; } // Driver code static void Main(string[] args) { Console.WriteLine(FindDigits(4, 16)); Console.WriteLine(FindDigits(5, 8)); Console.WriteLine(FindDigits(12, 16)); Console.WriteLine(FindDigits(19, 13)); }}}// This code is contributed by sarojmcy2e |
Javascript
// Function to convert a number to a given basefunction toBase(num, base) { const digits = "0123456789ABCDEF"; let res = ""; while (num > 0) { res = digits[num % base] + res; num = Math.floor(num / base); } return res;}// Function to find the length of n! in base Bfunction findDigits(n, b) { let fact = 1; for (let i = 2; i <= n; i++) { fact *= i; } const fact_base_b = toBase(fact, b); let count = 0; while (fact > 0) { count++; fact = Math.floor(fact / b); } return count;}// Driver codeconsole.log(findDigits(4, 16));console.log(findDigits(5, 8));console.log(findDigits(12, 16));console.log(findDigits(19, 13)); |
Output
2 3 8 16
Time Complexity: O(n*log(n)*log(B)), where n is the value of the given number and B is the base.
Auxiliary Space: O(n), as we are storing the factorial of the given number in a vector of size n.
Approach:
In order to solve the problem we use Kamenetsky’s formula which approximates the number of digits in a factorial
f(x) = log10( ((n/e)^n) * sqrt(2*pi*n))
The number of digits in n to the base b is given by logb(n) = log10(n) / log10(b). Hence, by using properties of logarithms, the number of digits of factorial in base b can be obtained by
f(x) = ( n* log10(( n/ e)) + log10(2*pi*n)/2 ) / log10(b)
This approach can deal with large inputs that can be accommodated in a 32-bit integer and even beyond that!
Below code is the implementation of the above idea :
C++
// A optimised program to find the // number of digits in a factorial in base b#include <bits/stdc++.h>using namespace std;// Returns the number of digits present // in n! in base b Since the result can be large// long long is used as return typelong long findDigits(int n, int b){ // factorial of -ve number // doesn't exists if (n < 0) return 0; // base case if (n <= 1) return 1; // Use Kamenetsky formula to calculate // the number of digits double x = ((n * log10(n / M_E) + log10(2 * M_PI * n) / 2.0)) / (log10(b)); return floor(x) + 1;}// Driver Codeint main(){ //calling findDigits(Number, Base) cout << findDigits(4, 16) << endl; cout << findDigits(5, 8) << endl; cout << findDigits(12, 16) << endl; cout << findDigits(19, 13) << endl; return 0;} |
Java
// A optimised program to find the // number of digits in a factorial in base bimport java.io.*;public class GFG{ // Returns the number of digits present // in n! in base b Since the result can be large// long is used as return typestatic long findDigits(int n, int b){ // factorial of -ve number // doesn't exists if (n < 0) return 0; // base case if (n <= 1) return 1; double M_PI = 3.141592; double M_E = 2.7182; // Use Kamenetsky formula to calculate // the number of digits double x = ((n * Math.log10(n / M_E) + Math.log10(2 * M_PI * n) / 2.0)) / (Math.log10(b)); return (long) (Math.floor(x) + 1);} // Driver Codepublic static void main(String[] args){ //calling findDigits(Number, Base) System.out.print(findDigits(4, 16) +"\n"); System.out.print(findDigits(5, 8) +"\n"); System.out.print(findDigits(12, 16) +"\n"); System.out.print(findDigits(19, 13) +"\n");}}// This code is contributed by 29AjayKumar |
Python 3
from math import log10,floor# A optimised program to find the # number of digits in a factorial in base b# Returns the number of digits present # in n! in base b Since the result can be large# long long is used as return typedef findDigits(n, b): # factorial of -ve number # doesn't exists if (n < 0): return 0 M_PI = 3.141592 M_E = 2.7182 # base case if (n <= 1): return 1 # Use Kamenetsky formula to calculate # the number of digits x = ((n * log10(n / M_E) + log10(2 * M_PI * n) / 2.0)) / (log10(b)) return floor(x) + 1# Driver Codeif __name__ == '__main__': #calling findDigits(Number, Base) print(findDigits(4, 16)) print(findDigits(5, 8)) print(findDigits(12, 16)) print(findDigits(19, 13))# This code is contributed by Surendra_Gangwar |
C#
// A optimised C# program to find the // number of digits in a factorial in base b using System;class GFG{ // Returns the number of digits present // in n! in base b Since the result can be large // long is used as return type static long findDigits(int n, int b) { // factorial of -ve number // doesn't exists if (n < 0) return 0; // base case if (n <= 1) return 1; double M_PI = 3.141592; double M_E = 2.7182; // Use Kamenetsky formula to calculate // the number of digits double x = ((n * Math.Log10(n / M_E) + Math.Log10(2 * M_PI * n) / 2.0)) / (Math.Log10(b)); return (long) (Math.Floor(x) + 1); } // Driver Code public static void Main(string[] args) { // calling findDigits(Number, Base) Console.WriteLine(findDigits(4, 16)); Console.WriteLine(findDigits(5, 8)); Console.WriteLine(findDigits(12, 16)); Console.WriteLine(findDigits(19, 13)); } } // This code is contributed by Yash_R |
Javascript
<script>// A optimised program to find the // number of digits in a factorial in base b// Returns the number of digits present // in n! in base b Since the result can be large// long long is used as return typefunction findDigits(n, b){ // factorial of -ve number // doesn't exists if (n < 0) return 0; // base case if (n <= 1) return 1; var M_PI = 3.141592; var M_E = 2.7182; // Use Kamenetsky formula to calculate // the number of digits var x = ((n * Math.log10(n / M_E) + Math.log10(2 * M_PI * n) / 2.0)) / (Math.log10(b)); return Math.floor(x) + 1;}// Driver Code// calling findDigits(Number, Base)document.write(findDigits(4, 16) + "<br>");document.write( findDigits(5, 8) + "<br>");document.write( findDigits(12, 16) + "<br>");document.write( findDigits(19, 13) + "<br>");// This code is contributed by rutvik_56.</script> |
Output
2 3 8 16
Time Complexity: O(1)
Auxiliary Space: O(1)
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!
