फॅक्टोरियल ट्रेलिंग झिरोज लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले ब्लूमबर्ग
गणित

समस्या विधान

या समस्येमध्ये आम्हाला एनमध्ये किती ट्रेलिंग झीरो असतील हे शोधून काढावे लागेल!
इनपुट म्हणून दिले.

जसे की 5 मध्ये एक पिछाडीवर शून्य आहे!
एक्सएनयूएमएक्स! = एक्सएनयूएमएक्स * एक्सएनयूएमएक्स * एक्सएनयूएमएक्स * एक्सएनयूएमएक्स * एक्सएनयूएमएक्स = एक्सएनयूएमएक्स

उदाहरण

n = 3
0

स्पष्टीकरण: 3! = 6, अनुगामी शून्य नाही

n = 0
0

स्पष्टीकरण: 0! = 1, अनुगामी शून्य नाही

 

एन मध्ये पिछाडीवर असलेल्या शून्यांची संख्या शोधण्यासाठी! , एन ची गणना करणे हा एक सोपा मार्ग आहे! आणि शेवटी किती शून्य आहेत ते तपासा. हे संख्या १० चे भागाकार करत आहे की नाही हे तपासून आपण उर्वरित ० मिळवितो आणि नंतर शेवटचे शून्य १० भागाकारून काढून टाकू. प्रत्येक वेळी शून्याच्या बरोबरी होईपर्यंत आपण हे मोजू शकतो.

परंतु हा दृष्टीकोन सोप्या पूर्णांसह व्यावहारिक नाही कारण आम्हाला माहित आहे! खूप मोठी संख्या आहे. सी ++ आणि जावा मध्ये साधा पूर्णांक आकार 64 2-बिट इतका आहे जो पूर्णांक केवळ २ - of^ - १ च्या मर्यादेपर्यंत संचयित करू शकतो जो अंदाजे 63 ^ 1 आहे. जावा मध्ये आम्ही n सारख्या मोठ्या संख्येने संग्रहित करण्यासाठी बिगइंटेजर वर्ग वापरू शकतो. परंतु या क्रूर शक्ती दृष्टीकोनात मोठी वेळ आणि अवकाश जटिलता आहे.

येथे आम्ही एन मध्ये मागील शून्य शोधण्यासाठी कार्यक्षम निराकरण चर्चा करणार आहोत!

दृष्टीकोन 1 (5 चे मोजण्याचे घटक)

आम्ही असे म्हणू शकतो की ट्रेलिंग झिरोची एकूण संख्या त्या संख्येचा 10 गुण किती वेळा मोजावी तितकी असेल. आणि आम्हाला माहित आहे की प्रत्येक 10 हे दोन आणि 2 च्या दोन मुख्य संख्येच्या उत्पादनाचे बनलेले आहेत.
तर संख्येत 2 चे किती घटक आहेत हे शोधून काढले तर. त्याचप्रमाणे 5 चे किती घटक आहेत. मग आपण असे म्हणू शकतो की यापैकी प्रत्येकजण 10 च्या बरोबरीने उत्पादन तयार करेल. म्हणूनच मागील अनुगामी शून्यांची संख्या कमीतकमी (2 ची गणना, 5 ची गणना) असेल.

आता आम्हाला हे घटक एन मध्ये मोजावे लागतील.
एन! = 1 * 2 * 3… .. * (एन -1) * एन

तर आम्ही 2 ते एन पर्यंत सर्व संख्या पुनरावृत्ती करू (2 ने वाढत जाईल कारण त्या संख्या आहेत ज्यात कमीतकमी एक 2 असेल).
प्रत्येक संख्येसाठी आम्ही त्या संख्येच्या घटकांनुसार 2 ची गणना शोधण्यासाठी 2 ने भागाकार होईपर्यंत त्यास 2 ने वारंवार विभाजीत करू.
त्याचप्रमाणे त्या संख्येतील 5 च्या मोजणीसाठी आपण तेच करू.
आता आम्ही या दोन गणांमधून किमान परत करू.

हे कार्य करते परंतु आम्ही त्यास थोडेसे अनुकूलित देखील करू शकतो. आम्ही विश्लेषण करू शकतो की आपल्याकडे 1 ते एन पर्यंत संख्या आहे, म्हणून आम्हाला नेहमी 2 ची शक्ती 5 च्या सामर्थ्यापेक्षा जास्त मिळू शकेल.
4 पर्यंत आम्हाला दोन संख्या प्राप्त होतात ज्यात घटक 2 आहेत (2 आणि 4). 5 वर घटक म्हणून प्रथम क्रमांक मिळविला. तर हे समान आणि वाढत्या मोजणीच्या फरकाने पुढे जाईल. येथे एक व्हिज्युअलायझेशन आहे जे स्पष्ट करते की 5 घटक आणि 2 घटकांमधील घनता कशी भिन्न आहे.

फॅक्टोरियल ट्रेलिंग झिरोज लीटकोड सोल्यूशन

म्हणून आम्ही असा निष्कर्ष काढू शकतो की 2 ची गणना नेहमी एन मध्ये 5 च्या मोजणीपेक्षा जास्त असते.
म्हणून आम्हाला फक्त 5 ची गणना शोधणे आवश्यक आहे आणि ते उत्तर असेल. अशा प्रकारे आम्ही कार्य अर्ध्याने कमी करतो.

फॅक्टोरियल ट्रेलिंग झिरोज लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

int trailingZeroes(int n) 
{
    int fives=0;
    for(int i=5;i<=n;i+=5)
    {
        int x=i;
        while(x>0 && x%5==0)
        {
            ++fives;
            x/=5;
        }
    }
    return fives;
}

int main() 
{
   cout<<trailingZeroes(5)<<endl;
   return 0; 
}
1

जावा कार्यक्रम

class Rextester{
    
    public static int trailingZeroes(int n) 
    {
        int fives=0;
        for(int i=5;i<=n;i+=5)
        {
            int x=i;
            while(x>0 && x%5==0)
            {
                ++fives;
                x/=5;
            }
        }
        return fives;
    }
    
  public static void main(String args[])
    {    	
    System.out.println(trailingZeroes(5));
    }
}
1

फॅक्टोरियल ट्रेलिंग झिरोज लीटकोड सोल्यूशनसाठी कॉम्प्लेक्सिटी विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन): एन पर्यंत पाचच्या सर्व गुणाकारांवर पुनरावृत्ती करू. हे पंचांची गणना शोधण्यासाठी आम्ही प्रत्येक घटकासाठी लॉग (एन) घेत आहोत असे दिसते. परंतु हे ओ (१) चे प्रमाणिकरण करते कारण आम्ही तपासलेल्या बर्‍याच मोठ्या संख्येमध्ये केवळ पाच घटक असतात. म्हणून एकूण वेळ जटिलता ओ (एन) म्हणून राहील.

स्पेस कॉम्प्लेक्सिटी 

ओ (1): कोणतीही अतिरिक्त मेमरी वापरली जात नाही.

दृष्टीकोन 2 (5 कार्यक्षमतेची मोजणी करणारे घटक)

वरील पध्दतीमध्ये आम्ही पाहिले की आम्हाला केवळ दिलेली एन च्या घटक म्हणून 5 ची गणना शोधणे आवश्यक आहे. वरील पध्दतीमध्ये आम्ही 5 च्या सर्व गुणाकारांवर पळ काढला आणि प्रत्येक संख्येसाठी 5 ची मोजणी जोडली आणि आमची उत्तरे रेषीय वेळेत मिळाली. आम्ही एक अंतिम निरीक्षण करू जे आम्हाला लॉजिकिथमिक वेळेत उत्तरांची गणना करण्यास अनुमती देईल.

एन मध्ये! (म्हणजे 1 ते एन पर्यंत) आमच्याकडे काही संख्या आहेत ज्यांना 5 ने भाग करणे शक्य नाही (0 च्या मोजणीसाठी 5 योगदान देणे), मग आपल्याकडे काही संख्या आहेत ज्या 5 ने भागाकार आहेत (प्रत्येकाने एका संख्येने योगदान देत आहे), मग आपल्याकडे संख्या आहेत ज्याद्वारे विभाजनीय आहेत २ ((या वेळी या बर्‍याच संख्येमधून एक अतिरिक्त योगदान), त्यानंतर १२ by ने भाग घेता येईल (या पैकी एक अतिरिक्त योगदान), यासारखे.

मग आमची उत्तरे या सर्व योगदानाची बेरीज होतील.
आम्ही खाली या सर्व गोष्टींची बेरीज करू शकतो:
5 च्या एकूण संख्या = एन / 5 + एन / 25 + एन / 125 +…. वगैरे
हे भाजक n पेक्षा कमी होईपर्यंत जाईल कारण त्या नंतर अपूर्णशाचे अविभाज्य मूल्य शून्य होईल.

पाऊल:
5 सह विभाजक चल प्रारंभ करा.
चालवा लूप, प्रत्येक पुनरावृत्तीमध्ये निकालासाठी n / भाजक मूल्य जोडा आणि भाजक 5 ने गुणाकार करा. प्रत्येक क्रमांकापर्यंत लूप चालवा <एन.

फॅक्टोरियल ट्रेलिंग झिरोज लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

int trailingZeroes(int n) 
{
    int fives=0;
    int den=5;

    while(den <= n)
    {
       fives += n/den;
       den *= 5;
    }
    return fives;
}

int main() 
{
   cout<<trailingZeroes(5)<<endl;
   return 0; 
}
1

जावा कार्यक्रम

#include <bits/stdc++.h>
using namespace std;

int trailingZeroes(int n) 
{
    int fives=0;
    int den=5;

    while(den <= n)
    {
       fives += n/den;
       den *= 5;
    }
    return fives;
}

int main() 
{
   cout<<trailingZeroes(5)<<endl;
   return 0; 
}
1

फॅक्टोरियल ट्रेलिंग झिरोज लीटकोड सोल्यूशनसाठी कॉम्प्लेक्सिटी विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (लॉग (एन)): एन पेक्षा कमी होईपर्यंत आम्ही प्रत्येक वेळी 5 ने गुणाकार करीत आहोत. म्हणून पुनरावृत्तीची एकूण संख्या लॉग (एन) असेल.

स्पेस कॉम्प्लेक्सिटी 

ओ (1): कोणतीही अतिरिक्त मेमरी वापरली जात नाही.