একটি ফ্যাক্টরিয়াল নাম্বার এ কয়টি সংখ্যা আছে

  -প্রবলেমঃ

 একটি নাম্বার N দেওয়া থাকবে। ঐ নাম্বার N! কয়টি নাম্বার আছে সেটি বের করতে হবে।

ব্রোথ-ফোর্স সলিউশনঃ
নরমালি যদি আমাদের যদি এই প্রবলেম সলিশন করতে বলা হয় তাহলে আমাদের চিন্তুা অনুযায়ী যা করি তা হচ্ছে:

#include <bits/stdc++.h>
using namespace std;
int factorialDigit(int n)
{
    long long fact = 1;
    for ( int i = 2; i <= n; i++ ) {
        fact *= i;
    }
    int res=0; // Number of digit of n!
    while (fact) { //  Loop until fact becomes 0
        res++;
        fact/=10; // Remove last digit
    }
    return res;
}
int main ()
{
    int n;
    cin >>n;
    cout << factorialDigit(n) << endl;
}

কিন্তু এই কোড টা কাজ করবে N<=20 । যদি N>=20 থেকে বেশি নেই তাইলে long long ব্যবহার করলে overflow হবে। তাহলে কি আমরা বিগ ইন্টিজার ব্যবহার করতে পারি?

লগারিদম এর মাধ্যমে ফ্যাক্টরিয়ালের সংখ্যা বের করা:
নিচে কিছু লগারিদম ভ্যালু দিয়ে নাম্বার বের করা হয়েছে।লগারিদম সাথে নাম্বারের সংখ্যা সম্পূর্ক নিচে দেওয়া হল।

log10(x)=y
log10(1)=0
log10(10)=1
log10(100)=2
log10(1000)=3
log10(10000)=4

x ইনক্রিমেন্ট করার সাথে সাথে y ইনক্রিমেন্ট করছে। প্রতিবার  x  কে 10 দিয়ে ভাগ করা হচ্ছে এবং যেই y রেজাল্ট বের হচ্ছে সেটা 1 করে বাড়ছে।উপরোক্ত টেবিল অনুযায়ী নিচের কিছু উদাহরন দেখলে পরিস্কার হয়ে যাবে।
যদি log10(100)=2 এবং log10(1000)=3 হয় তাহলে X সকল ভ্যালুর জন্য কন্ডিশন হবে 100<X<1000 এবং Y সকল ভ্যালুর জন্য কন্ডিশন হবে y<2<3.

log10(100)=2
log10(150)=2.17609125906
log10(500)=2.69897000434
log10(999)=2.99956548823

 নাম্বারের কতগুলো সংখ্যা আছে তা X এবং Y মধ্যে একটা সম্পূর্ক আছে । যদি ভ্যালুর জন্য
 2*XXX হয় তাহলে X ও হবে 2+1=3 সংখ্যা।

                                 সুতরাং একটি  নাম্বারের  সংখ্যা যদি X হয় তাহলে: x=⌊log10(x)⌋+1

থিওরি অনুযায়ী যদি 1 থেকে  log10(x)  যোগ করতে চাই তাহলে লগ এর সাথে ⌊⌋ ফ্লোর মাধ্যমে যোগ করতে হবে।আর সুক্ষতার পরিমাপের জন্য eps ব্যবহার করতে হবে । eps দিয়ে কি করা হয়? eps দিয়ে সূক্ষতার পরিমাপ করা হয়।
যেমন আমাদের log10(100)=1.9999999 রেজাল্ট আসে আর 1.9999999 মানে হচ্ছে 2 । নিচের কোডটা দেখলে আরেকটু পরিস্কার হয়ে যাবে।
     int numberDigit(int n )
    {

    int wrongAnswer=log10(n)+1; // This may give wrong answer sometimes.
    int rightAnswer=log10(n)+1+eps; // This is right.
    return rightAnswer;
    }

লগারিদম মাধ্যমে সলিশনঃ

লগারিদম এর মাধ্যমে সহজে বের করা যায়ে একটি নাম্বার এর শেষে কয়টি সংখ্যা আছে। এখন প্রশ্ন হচেছ লগারিদম কি? আমরা স্কুলে ছোটবেলা লগারিদম সম্পর্কে কিছুটা জেনে আসছি । লগারিদম এর একটি নাম্বার x থাকে এবং বেস হচ্ছে y এবং একটি বাস্তব সংখ্যা b থাকে যা হল x=y^b 

2 এ

       log101234=3.0913151597 and 103.0913151597=1234

লগারিদম এ বেস নাম্বার খুবই দরকারি। N! শেষে কয়টি নাম্বার আছে যদি ডেসিমেল এ বের করতে চাই তাহলে এটি বেস 10 এ কাজ করবে।

তাহলে লগারিদম থেকে বের করা টেকনিক হচ্ছে: লগারিদম আইডি থেকে কিভাবে N! বের করতে পারি? যদি x=log10(N !)হয় তাহলে আমাদের উত্তর হবে res=⌊x⌋+1 
x=log10(N!)
 x=log10(1×2×3×...×N)



∴x=log10(1)+log10(2)+log10(3)+...+log10(N)






























লগারিদম সূত্র : log10(ab)=log10(a)+log10(b)

এখন আমাদের কোনো রকম চিন্তা ছাড়াই N! ক্যালকুলেশন না করেই শুধু লগ ভ্যালু যোগ করে
বের করে দিলেই আমরা রেজাল্ট পেয়ে যাব।
//complexiey O(N)

#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
int factorization_fact(int num)
{
    double x = 0;
    for(int i=1; i<=num; i++){
        x=x+log10(i);
    }
    int res = x+1+eps;
    return res;
}
int main ()
{
    int n;
    cin >>n;
    cout << factorization_fact(n) << endl;
}

..