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


कठिनाई स्तर आसान
में अक्सर पूछा ब्लूमबर्ग
मठ

समस्या का विवरण

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

जैसे 5 में एक अनुगामी शून्य है!
5! = 5 * 4 * 3 * 2 * 1 = 120

उदाहरण

n = 3
0

व्याख्या: ३! = 3, कोई अनुगामी शून्य नहीं

n = 0
0

व्याख्या: ३! = 0, कोई अनुगामी शून्य नहीं

 

N में अनुगामी शून्य की संख्या ज्ञात करने के लिए! , एन की गणना करने के लिए एक सरल तरीका है! और जांच करें कि अंत में कितने शून्य हैं। यह हम केवल जाँच करके कर सकते हैं कि संख्या को 10 से भाग देने पर हम शेष 0 हो जाते हैं और फिर 10. से विभाजित करके अंतिम शून्य को हटाते हैं। हम इसे तब तक गिन सकते हैं जब तक हम प्रत्येक बार शून्य के बराबर शेष नहीं हो जाते।

लेकिन यह दृष्टिकोण सरल पूर्णांकों के साथ व्यावहारिक नहीं है क्योंकि हम n जानते हैं! एक बहुत बड़ी संख्या है। C ++ और Java सरल पूर्णांक आकार में 64-बिट सबसे अच्छा है जो केवल पूर्णांक को 2 ^ 63 - 1. की सीमा तक संग्रहीत कर सकता है जो कि 10 ^ 18 तक अनुमानित है। जावा में हम बड़ी संख्या को n की तरह स्टोर करने के लिए BigInteger वर्ग का उपयोग कर सकते हैं! लेकिन इस जानवर बल दृष्टिकोण में बड़े समय और स्थान की जटिलता है।

यहाँ हम n में अनुगामी शून्य को खोजने के लिए कुशल समाधान पर चर्चा करने जा रहे हैं!

दृष्टिकोण 1 (5 के गुणनखंड)

हम कह सकते हैं कि अनुगामी शून्य की कुल संख्या इस बात की गणना के बराबर होगी कि 10 कितनी संख्या का कारक है। और हम जानते हैं कि प्रत्येक 10 दो प्रमुख संख्याओं 2 और 5 के उत्पाद से बनता है।
इसलिए अगर हमें पता चले कि संख्या में 2 के कितने कारक हैं। इसी तरह 5 के कितने कारक हैं। फिर हम कह सकते हैं कि इनमें से प्रत्येक उत्पाद को 10 के बराबर बनाने के लिए गठबंधन करेगा। इसलिए अनुगामी शून्य की कुल संख्या न्यूनतम के बराबर होगी (2 की गिनती, 5 की गिनती)।

अब हमें n में इन कारकों को गिनना होगा!
n! = 1 * 2 * 3… .. * (एन -1) * एन

इसलिए हम 2 से n तक की सभी संख्याओं को बढ़ाएँगे (2 से बढ़ाएँ क्योंकि वे संख्याएँ हैं जिनमें कम से कम एक 2 अंक होते हैं)।
प्रत्येक संख्या के लिए हम बार-बार इसे 2 से विभाजित करेंगे, जब तक कि उस संख्या के गुणन में 2 की गिनती ज्ञात करने के लिए 2 से विभाज्य न हो।
इसी प्रकार उस संख्या में 5 की गिनती ज्ञात करने के लिए हम वही कार्य करेंगे।
अब हम इन दो में से न्यूनतम को गिनेंगे।

यह काम करता है, लेकिन हम इसे थोड़ा सा अनुकूलित भी कर सकते हैं। हम विश्लेषण कर सकते हैं कि हमारे पास 1 से n तक संख्याएं हैं, इसलिए हमें हमेशा 2 की शक्तियों से अधिक 5 शक्तियां मिलेंगी।
जैसे 4 तक हमें दो नंबर मिलते हैं जिनमें 2 एक कारक के रूप में होते हैं (2 और 4)। 5 पर हमें फैक्टर के रूप में 5 नंबर मिलते हैं। तो यह समान (बढ़ते) गिनती अंतर के साथ और आगे बढ़ेगा। यहाँ एक दृश्य है जो बताता है कि 2 कारकों और 5 कारकों के बीच घनत्व कैसे भिन्न होता है।

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

इसलिए हम यह निष्कर्ष निकाल सकते हैं कि 2 की गिनती हमेशा n में 5 की गिनती से अधिक होती है!
इसलिए हमें केवल 5 की गिनती खोजने की आवश्यकता है और यह ans होगा। इस तरह हम कार्य को आधा कर देते हैं।

फैक्टरियल ट्रेलिंग जीरो लीटकोड सॉल्यूशन के लिए कार्यान्वयन

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

फैक्टरियल ट्रेलिंग जीरो लीटकोड सॉल्यूशन के लिए जटिलता विश्लेषण

समय जटिलता

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

अंतरिक्ष जटिलता 

ओ (1): किसी भी अतिरिक्त मेमोरी का उपयोग नहीं किया जाता है।

दृष्टिकोण 2 (कुशलता से 5 की गिनती के कारक)

उपरोक्त दृष्टिकोण में हमने देखा कि हमें दिए गए n के कारक के रूप में केवल 5 की गिनती खोजने की आवश्यकता है। उपर्युक्त दृष्टिकोण में हमने 5 के सभी गुणकों पर लूप किया और प्रत्येक संख्या के लिए 5 की गिनती को जोड़ा और रैखिक समय में हमारी ans प्राप्त की। हम एक अंतिम अवलोकन करेंगे, जो हमें लघुगणक समय में ans की गणना करने की अनुमति देगा।

सराय! (अर्थात 1 से n तक) हमारे पास कुछ संख्याएँ हैं जो 5 से विभाज्य नहीं हैं (0 की गिनती के लिए 5), तो हमारे पास कुछ संख्याएँ हैं जो 5 से विभाज्य हैं (प्रत्येक एक गणना में योगदान करते हैं), फिर हमारे पास संख्याएँ हैं जो विभाज्य हैं 25 (इस समय इन कई नंबरों में से एक अतिरिक्त योगदान), फिर 125 से विभाज्य (इन में से एक अतिरिक्त योगदान), इस तरह और इसी तरह।

तब हमारा एएन इन सभी योगदानों का योग होगा।
हम इन सभी को नीचे के रूप में जोड़ सकते हैं:
5 की कुल संख्या = n / 5 + n / 25 + n / 125 +…। जल्द ही
यह तब तक जाएगा जब तक भाजक n से कम न हो जाए क्योंकि उसके बाद अंश का अभिन्न मूल्य शून्य होगा।

कदम:
5 के साथ भाजक चर को प्रारंभ करें।
एक रन पाश, प्रत्येक पुनरावृत्ति में परिणाम के लिए n / हर का मान जोड़ें और हर से 5 को गुणा करें। हर को हर करें।

फैक्टरियल ट्रेलिंग जीरो लीटकोड सॉल्यूशन के लिए कार्यान्वयन

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

फैक्टरियल ट्रेलिंग जीरो लीटकोड सॉल्यूशन के लिए जटिलता विश्लेषण

समय जटिलता

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

अंतरिक्ष जटिलता 

ओ (1): किसी भी अतिरिक्त मेमोरी का उपयोग नहीं किया जाता है।