కారకమైన వెనుకంజలో ఉన్న సున్నాలు లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది బ్లూమ్బెర్గ్
మఠం

సమస్యల నివేదిక

ఈ సమస్యలో n లో ఎన్ని వెనుకంజలో ఉన్న సున్నాలు ఉంటాయో తెలుసుకోవాలి!
N ను ఇన్‌పుట్‌గా ఇచ్చారు.

5 లో ఒక వెనుకంజలో ఉన్నట్లుగా!
5! = 5 * 4 * 3 * 2 * 1 = 120

ఉదాహరణ

n = 3
0

వివరణ: 3! = 6, వెనుకంజలో లేదు

n = 0
0

వివరణ: 0! = 1, వెనుకంజలో లేదు

 

N లో వెనుకంజలో ఉన్న సున్నాల సంఖ్యను కనుగొనడానికి! , n ను లెక్కించడం ఒక సాధారణ మార్గం! మరియు చివరిలో ఎన్ని సున్నాలు ఉన్నాయో తనిఖీ చేయండి. సంఖ్యను 10 ద్వారా భాగించడం ద్వారా మనకు మిగిలిన 0 లభిస్తుందో లేదో తనిఖీ చేసి, చివరి సున్నాను 10 ద్వారా విభజించడం ద్వారా దీన్ని తొలగించవచ్చు. ప్రతిసారీ సున్నాకి సమానమైనంత వరకు మనం దీన్ని లెక్కించవచ్చు.

కానీ ఈ విధానం సాధారణ పూర్ణాంకాలతో ఆచరణాత్మకం కాదు ఎందుకంటే మనకు n తెలుసు! చాలా పెద్ద సంఖ్య. సి ++ మరియు జావాలో సాధారణ పూర్ణాంక పరిమాణం 64-బిట్ ఉత్తమంగా ఉంటుంది, ఇది పూర్ణాంకాన్ని 2 ^ 63 - 1 పరిమితికి మాత్రమే నిల్వ చేయగలదు. ఇది సుమారు 10 ^ 18 కు ఉంటుంది. జావాలో మనం బిగ్‌ఇంటెగర్ క్లాస్‌ని ఉపయోగించి n! కానీ ఈ బ్రూట్ ఫోర్స్ విధానం పెద్ద సమయం మరియు స్థల సంక్లిష్టతను కలిగి ఉంది.

ఇక్కడ మనం n లో వెనుకంజలో ఉన్న సున్నాలను కనుగొనటానికి సమర్థవంతమైన పరిష్కారం గురించి చర్చించబోతున్నాం!

అప్రోచ్ 1 (5 యొక్క లెక్కింపు కారకాలు)

వెనుకంజలో ఉన్న సున్నాల సంఖ్య ఆ సంఖ్యకు 10 సార్లు ఎన్నిసార్లు లెక్కించాలో సమానంగా ఉంటుందని మేము చెప్పగలం. మరియు ప్రతి 10 రెండు ప్రధాన సంఖ్యలు 2 మరియు 5 యొక్క ఉత్పత్తి నుండి ఏర్పడతాయని మనకు తెలుసు.
కాబట్టి 2 యొక్క ఎన్ని కారకాలు సంఖ్యలో ఉన్నాయో తెలుసుకుంటే. అదేవిధంగా 5 యొక్క ఎన్ని అంశాలు ఉన్నాయి. అప్పుడు వీటిలో ప్రతి ఒక్కటి కలిపి ఉత్పత్తిని 10 కి సమానంగా చేస్తాయని మనం చెప్పగలం. అందువల్ల వెనుకంజలో ఉన్న మొత్తం సున్నాల సంఖ్య కనిష్టానికి సమానంగా ఉంటుంది (2 ల సంఖ్య, 5 ల సంఖ్య).

ఇప్పుడు మనం ఈ కారకాలను n లో లెక్కించాలి.
n! = 1 * 2 * 3… .. * (n-1) * n

కాబట్టి మేము 2 నుండి n వరకు ఉన్న అన్ని సంఖ్యలపై మళ్ళిస్తాము (2 ద్వారా పెంచడం ఎందుకంటే అవి కనీసం ఒక 2 లను కలిగి ఉన్న సంఖ్యలు).
ప్రతి సంఖ్యకు ఆ సంఖ్యను కారకం చేయడంలో 2 యొక్క గణనను కనుగొనడానికి 2 ద్వారా విభజించబడే వరకు దాన్ని 2 ద్వారా పదేపదే విభజిస్తాము.
అదేవిధంగా ఆ సంఖ్యలోని 5 ల సంఖ్యను కనుగొనడానికి మేము అదే పని చేస్తాము.
ఇప్పుడు మేము ఈ రెండు గణనలలో కనీస మొత్తాన్ని తిరిగి ఇస్తాము.

ఇది పనిచేస్తుంది కాని మనం దాన్ని కొద్దిగా ఆప్టిమైజ్ చేయవచ్చు. మనకు 1 నుండి n వరకు సంఖ్యలు ఉన్నాయని విశ్లేషించవచ్చు, కాబట్టి మేము ఎల్లప్పుడూ 2 యొక్క అధికారాలను 5 యొక్క అధికారాల కంటే ఎక్కువగా పొందుతాము.
4 వరకు మాదిరిగా మనకు 2 కారకాలు (2 మరియు 4) ఉన్న రెండు సంఖ్యలు లభిస్తాయి. 5 వద్ద మనకు మొదటి సంఖ్య 5 కారకంగా ఉంటుంది. కాబట్టి ఇది సారూప్య (పెరుగుతున్న) గణన వ్యత్యాసంతో కొనసాగుతుంది. 2 కారకాలు మరియు 5 కారకాల మధ్య సాంద్రత ఎలా విభిన్నంగా ఉంటుందో వివరించే విజువలైజేషన్ ఇక్కడ ఉంది.

కారకమైన వెనుకంజలో ఉన్న సున్నాలు లీట్‌కోడ్ పరిష్కారం

అందువల్ల 2 యొక్క సంఖ్య ఎల్లప్పుడూ n లో 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

ఫ్యాక్టోరియల్ ట్రెయిలింగ్ జీరోస్ లీట్‌కోడ్ సొల్యూషన్ కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) : మేము n వరకు ఐదు గుణకాలపై మళ్ళిస్తున్నాము. ఫైవ్‌ల సంఖ్యను కనుగొనడానికి మేము లాగ్ (ఎన్) సమయం తీసుకుంటున్న ప్రతి మూలకం కోసం ఇది కనిపిస్తుంది. కానీ ఇది O (1) కు రుణమాఫీ చేస్తుంది ఎందుకంటే మేము తనిఖీ చేసిన అధిక సంఖ్యలో సంఖ్యలు ఐదు కారకాలను మాత్రమే కలిగి ఉంటాయి. అందువల్ల మొత్తం సమయ సంక్లిష్టత O (n) గా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత 

ఓ (1): అదనపు మెమరీ ఉపయోగించబడదు.

అప్రోచ్ 2 (5 యొక్క కారకాలను సమర్థవంతంగా లెక్కించడం)

పై విధానంలో, ఇచ్చిన n యొక్క కారకంగా 5 యొక్క గణనను మాత్రమే కనుగొనవలసి ఉందని మేము చూశాము. పై విధానంలో మేము 5 యొక్క అన్ని గుణకాలపై లూప్ చేసాము మరియు ప్రతి సంఖ్యకు 5 యొక్క గణనను జోడించాము మరియు సరళ సమయంలో మా జవాబులను పొందాము. మేము ఒక చివరి పరిశీలన చేస్తాము, ఇది లాగరిథమిక్ సమయంలో జవాబులను లెక్కించడానికి అనుమతిస్తుంది.

N లో! . 1 (ఈసారి ఈ అనేక సంఖ్యల నుండి ఒక అదనపు సహకారం), తరువాత 5 ద్వారా విభజించవచ్చు (వీటి నుండి ఒక అదనపు సహకారం), ఇలా మరియు మొదలైనవి.

అప్పుడు మా అన్స్ ఈ అన్ని రచనల మొత్తం అవుతుంది.
ఇవన్నీ మేము ఈ క్రింది విధంగా సంకలనం చేయవచ్చు:
5 యొక్క మొత్తం సంఖ్య = n / 5 + n / 25 + n / 125 +…. కాబట్టి
హారం n కంటే తక్కువగా ఉండే వరకు ఇది వెళ్తుంది ఎందుకంటే ఆ భిన్నం యొక్క సమగ్ర విలువ సున్నా అవుతుంది.

దశ:
5 తో హారం వేరియబుల్ ప్రారంభించండి.
ఒక రన్ లూప్, ప్రతి పునరావృతంలో ఫలితానికి n / హారం విలువను జోడించి, హారం 5 ద్వారా గుణించాలి. హారం <n వరకు లూప్‌ను అమలు చేయండి.

ఫ్యాక్టోరియల్ ట్రెయిలింగ్ జీరోస్ లీట్‌కోడ్ సొల్యూషన్ కోసం అమలు

సి ++ ప్రోగ్రామ్

#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)): మేము n కంటే తక్కువగా ఉండే వరకు ప్రతిసారీ హారం 5 ద్వారా గుణిస్తున్నాము. అందువల్ల మొత్తం పునరావృత సంఖ్య లాగ్ (n) అవుతుంది.

అంతరిక్ష సంక్లిష్టత 

ఓ (1): అదనపు మెమరీ ఉపయోగించబడదు.