காரணி பின்னால் பூஜ்ஜியங்கள் லீட்கோட் தீர்வு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது ப்ளூம்பெர்க்
கணித

சிக்கல் அறிக்கை

இந்த சிக்கலில் n இல் எத்தனை பின்னால் பூஜ்ஜியங்கள் இருக்கும் என்பதை நாம் கண்டுபிடிக்க வேண்டும்!
N உள்ளீடாக வழங்கப்பட்டது.

5 இல் ஒரு பின்னால் பூஜ்ஜியம் இருப்பது போல!
ஐந்து! = 5 * 5 * 4 * 3 * 2 = 1

உதாரணமாக

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 இன் எண்ணிக்கையைச் சேர்த்துள்ளோம், மேலும் எங்கள் பதில்களை நேரியல் நேரத்தில் பெற்றோம். ஒரு இறுதி அவதானிப்பை நாங்கள் செய்வோம், இது மடக்கை நேரத்தில் பதில்களைக் கணக்கிட அனுமதிக்கும்.

சத்திரம்! . 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

காரணி பின்தங்கிய பூஜ்ஜியங்களின் சிக்கலான பகுப்பாய்வு லீட்கோட் தீர்வு

நேர சிக்கலானது

ஓ (பதிவு (என்)): ஒவ்வொரு முறையும் n ஐ விடக் குறைவாக இருக்கும் வரை வகுப்பினை 5 ஆல் பெருக்குகிறோம். எனவே மறு செய்கையின் மொத்த எண்ணிக்கை பதிவு (n) ஆக இருக்கும்.

விண்வெளி சிக்கலானது 

ஓ (1): கூடுதல் நினைவகம் எதுவும் பயன்படுத்தப்படவில்லை.