Find the length of factorial of a number in any given base

0 0 7 minutes read

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 2

Input: 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 base
string 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 B
long 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 code
int 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 base
def 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 B
def 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 code
print(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 base
function 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 B
function 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 code
console.log(findDigits(4, 16));
console.log(findDigits(5, 8));
console.log(findDigits(12, 16));
console.log(findDigits(19, 13));

Output

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 type
long 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 Code
int 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 b
import 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 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)
    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 type
def 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 Code
if __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 type
function 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

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