फैक्टोरियल ट्रेलि Z शून्यहरू लेटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ ब्लूमबर्ग
गणित

समस्या वक्तव्य

यस समस्यामा हामीले पत्ता लगाउनुपर्नेछ कि एनमा कति ट्रेलि z शून्यहरू हुनेछन्!
इनपुटको रूपमा n दिइयो।

जस्तै 5 मा एक पछिल्लो शून्य छ!
पाँच! = १ * २ * * * * * = = १२०

उदाहरणका

n = 3
0

स्पष्टीकरण:!! =,, कुनै पछाडि शून्य छैन

n = 0
0

स्पष्टीकरण:!! =,, कुनै पछाडि शून्य छैन

 

एनमा पछिल्लो शुन्यहरूको संख्या पत्ता लगाउन! , एक सरल तरिका एन गणना गर्न हो! र अन्तमा कति शूनो छन् जाँच गर्नुहोस्। यो संख्या १० लाई भाँच्ने हो भने हामी बाँकी ० पाउँछौं र पछि अन्तिम शून्यलाई १० लाई भाग गरी हटाएर हामी यो गर्न सक्दछौं हामी प्रत्येक पटक शून्य बराबर नभएसम्म यसलाई गणना गर्न सक्छौं।

तर यो दृष्टिकोण सरल पूर्णांकको साथ व्यावहारिक छैन किनभने हामी n जान्दछौं! धेरै ठूलो संख्या हो। सी ++ र जाभा साधारण इन्टिजर साइज 64 2-बिटमा उत्तम हुन्छ जुन केवल २ ^ --^ - १ को सीमामा पूर्णांक भण्डार गर्न सक्दछ जुन १० Which १^ को अनुमानित हो। जाभामा हामी बिग ईन्टिगर कक्षा प्रयोग गर्न सक्दछौं एन जस्तै ठूलो संख्या भण्डार गर्न। तर यो जबरजस्ती दृष्टिकोण दृष्टिकोण ठूलो समय र अन्तरिक्ष जटिलता छ।

यहाँ हामी एन मा ट्रेलि! शून्य पत्ता लगाउन कुशल समाधान छलफल गर्न जाँदैछौं!

दृष्टिकोण १ (of को कारक गणना गर्दै)

हामी भन्न सक्छौं कि ट्रेलि z शून्यको कुल संख्या १० संख्याको गुणन बराबर कति हुनेछ। र हामीलाई थाहा छ कि प्रत्येक १० दुई र prime अ prime्कको गुणको गठन गरीएको छ।
त्यसोभए यदि हामी संख्याका २ कारकहरू कति छन् भन्ने फेला पार्यौं। त्यस्तै कति कारकहरु त्यहाँ छन्। त्यसोभए हामी भन्न सक्दछौं कि ती प्रत्येकले १० लाई बराबरको उत्पादन बनाउन मिल्छ। त्यसैले ट्रेलि। शून्यहरूको कूल संख्या न्यूनतम बराबर हुनेछ (२ को गणना,'s को गणना)।

अब हामीले यी कारकहरूलाई एनमा गणना गर्नुपर्दछ।
n! = १ * २ *…… .. * (n-१) * n

त्यसो भए हामी २ बाट n सम्म सबै नम्बरहरूमा पुनरावृत्ति गर्नेछौं (२ बढाउँदै किनकि ती संख्याहरू हुन् जसमा कम्तिमा एक २ हुन्छ)।
प्रत्येक संख्या को लागी हामी यसलाई दोहोर्याई २ बाट भाग्नेछौं जबसम्म यो २ बाट भाग नहुन्जेल २ को गणनालाई संख्याको कारकमा फर्काउँदैन।
त्यस्तै संख्यामा's को गणना पत्ता लगाउन हामी त्यहि काम गर्छौं।
अब हामी यी दुई गणना मध्ये न्यूनतम फिर्ता गर्नेछौं।

यसले कार्य गर्दछ तर हामी यसलाई थोरै अनुकूलन पनि गर्न सक्छौं। हामी विश्लेषण गर्न सक्छौं कि हामीसँग १ देखि n सम्म संख्याहरू छन्, त्यसैले हामी सँधै २ को शक्तिहरू 1 को शक्ति भन्दा बढी पाउनेछौं।
Till सम्म हामी दुई नम्बरहरू पाउँछौं जुन २ को एक कारक (२ र)) को रूपमा छन्। At मा हामी पहिलो नम्बर प्राप्त गर्दछौं factor गुणकको रूपमा। त्यसो भए यो क्रममा बढ्नेछ र यस्तै (बढ्दो) गणना भिन्नताका साथ यहाँ एक दृश्य छ कि कसरी वर्णन गर्दछ कि २ कारक र factors कारकहरू बीच घनत्व कसरी भिन्न छ।

फैक्टोरियल ट्रेलि Z शून्यहरू लेटकोड समाधान

त्यसकारण हामी यो निष्कर्षमा पुग्न सक्छौं कि २ को गणना सँधै n मा 2 को गणना भन्दा ठूलो हुन्छ।
त्यसैले हामीले's को मात्र गणना खोज्नु पर्छ र त्यो उत्तरहरू हुनेछ। यो तरिकाले हामी आधा कार्य कम गर्छौं।

फ्याक्टोरियल ट्रेलि Z शून्य लीटकोड समाधानको लागि कार्यान्वयन

C ++ कार्यक्रम

#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

फ्याक्टोरियल ट्रेलि Z शून्य लीटकोड समाधानको लागि जटिलता विश्लेषण

समय जटिलता

O (n): हामी n सम्म पाँचको गुणनहरूमा पुनरावृत्ति गर्दैछौं। यो प्रत्येक तत्वको जस्तै लाग्न सक्छ जुन हामीले लग (n) लिइरहेका छौं पाँचको गणना पत्ता लगाउन। तर यो ओ (१) मा परिशोधित गर्दछ किनकि हामीले जाँच गरेको संख्याको विशाल बहुमतले केवल पाँचको एक मात्र कारक समावेश गर्दछ। त्यसकारण कुल समय जटिलता O (n) को रूपमा रहन्छ।

ठाउँ जटिलता 

O (१): कुनै पनि अतिरिक्त मेमोरी प्रयोग गरिएको छैन।

दृष्टिकोण २ (2 वटा कुशलताका साथ गणनाका कारकहरू)

माथिको दृष्टिकोणमा हामीले देख्यौं कि हामीले n को गणना मात्र दिइएको एनको घटकको रूपमा फेला पार्नु पर्छ। माथिको दृष्टिकोणमा हामीले multip को सबै गुणनहरूमा लुप पार्यौं र प्रत्येक नम्बरका लागि's को गणना थप्‍यौं र लाइनियर समयमा हाम्रो उत्तरहरू प्राप्त गर्‍यौं। हामी एउटा अन्तिम अवलोकन गर्नेछौं जसले हामीलाई लगारिथमिक समयमा उत्तरहरू गणना गर्न अनुमति दिनेछ।

एनमा! (जस्तै १ देखि एन) हामीसँग केहि संख्याहरू छन् जुन by ले भाग गर्न मिल्दैन ('s को गणनाका लागि ० योगदान गर्दै), त्यसपछि हामीसँग केही संख्याहरू हुन्छन् जुन by (हरेक एक गणनालाई योगदान पुर्‍याउने) ले भाग गर्न मिल्छ, तब हामीसँग संख्याहरू हुन्छन् जुन विभाजित हुन्छन् २ ((यस पटक यी धेरै संख्याबाट एक अतिरिक्त योगदान), त्यसपछि १२ by बाट विभाज्य (यीबाट एक अतिरिक्त योगदान), यस्तै र यस्तै।

त्यसो भए हाम्रो उत्तरहरू यी सबै योगदानहरूको योगफल हुनेछ।
हामी यी सबैलाई तल तल जोड्न सक्छौं:
's को = n / + + n / २ + + n / १२ + + को कुल गणना। यस्तै
यो डिनोमिनेटर n भन्दा कम हुनु अघि जान्छ किनकी अंशको अभिन्न मान शून्य हुनेछ।

चरण:
Omin को साथ डाइनोमिनेटर भ्यारीएबल शुरु गर्नुहोस्।
चलाउनुहोस् लुप, प्रत्येक पुनरावृत्तिमा परिणाममा n / भाजक मान थप्नुहोस् र डिनोमिनेटरलाई। बाट गुणा गर्नुहोस्। भाजक <n सम्म लूप चलाउनुहोस्।

फ्याक्टोरियल ट्रेलि Z शून्य लीटकोड समाधानको लागि कार्यान्वयन

C ++ कार्यक्रम

#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

फ्याक्टोरियल ट्रेलि Z शून्य लीटकोड समाधानको लागि जटिलता विश्लेषण

समय जटिलता

O (लग (n)): हामी प्रत्येक पटक 5 ले गुणा गर्दछौं जबसम्म यो एन भन्दा कम हुन्छ। यसैले पुनरावृत्तिको कुल संख्या लग (n) हुनेछ।

ठाउँ जटिलता 

O (१): कुनै पनि अतिरिक्त मेमोरी प्रयोग गरिएको छैन।