စက်ရုံ Trailing သုည Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် ဘလွန်းဘာ့ဂ်
သင်္ချာ

ပြProbleနာဖော်ပြချက်

ဤပြproblemနာတွင် n တွင်မည်သည့်လမ်းကြောင်းမှသုညမည်မျှရှိသည်ကိုရှာဖွေရမည်။
input ကိုအဖြစ် n ပေးထားသည်။

လိုပဲတစ်ခုမှာနောက်ကွယ်မှသုည 5 ရှိ!
ငါး! = 5 * 5 * 4 * 3 * 2 = 1

နမူနာ

n = 3
0

ရှင်းလင်းချက် - ၃ ။ = 3, အဘယ်သူမျှမနောက်ကွယ်မှသုည

n = 0
0

ရှင်းလင်းချက် - ၃ ။ = 0, အဘယ်သူမျှမနောက်ကွယ်မှသုည

 

n ၏တွယ်ကပ်နေသောသုညကိုရှာရန်။ ရိုးရိုးရှင်းရှင်းနည်းလမ်းက n ကိုတွက်တာပါပဲ။ နှင့်အဆုံးမှာသုညမည်မျှစစ်ဆေးပါ။ ကိန်းကို ၁၀ နဲ့စားရင် ၁၀ ကျန်မယ်၊ ကျန်သုညကို ၁၀ နဲ့စားရင် ၁၀ နဲ့စားရင်ရမယ်။ ရတယ်။ ကျန်ချိန်ကိုသုညနဲ့ညီရင်ရမယ်။

သို့သော် n သည်ကျွန်ုပ်တို့သိသောကြောင့်၊ ဤချဉ်းကပ်မှုသည်ရိုးရှင်းသောကိန်းဂဏန်းများနှင့်လက်တွေ့မကျပါ။ အလွန်ကြီးမားတဲ့ကိန်းဂဏန်းတစ်ခုဖြစ်တယ်။ C ++ နှင့် Java တို့တွင် integer အရွယ်အစားသည်အကောင်းဆုံး 64-bit ဖြစ်သည်။ ၎င်းသည်ကိန်းဂဏန်းများကို 2 ^ 63 - 1 အကန့်အသတ်သာသိုလှောင်နိုင်သည်။ ၁၀ - ၁၈ နှင့်အနီးစပ်ဆုံးဖြစ်သည်။ java တွင် n ကဲ့သို့ကြီးမားသောနံပါတ်များကိုသိမ်းဆည်းရန် BigInteger အတန်းကိုသုံးနိုင်သည်။ သို့သော်ဤ brute force ချဉ်းကပ်မှုသည်အချိန်နှင့်နေရာရှုပ်ထွေးမှုများစွာရှိသည်။

ဤနေရာတွင် n ၏နောက်ကွယ်တွင်ရှိသောသုညများကိုရှာဖွေရန်ထိရောက်သောဖြေရှင်းချက်ကိုဆွေးနွေးပါမည်။

ချဉ်းကပ်မှု ၁ (၅ ၏ရေတွက်သည့်အချက်များ)

ကျွန်တော်တို့ပြောနိုင်တာကစုစုပေါင်း 10 သုညဟာဒီကိန်းရဲ့ဆခွဲကိန်းနဲ့ညီမယ်။ ပြီးတော့ ၁၀ ခုတိုင်းကိုနှစ်ဂဏန်း ၂ နဲ့ ၅ တို့ကထုတ်လုပ်တယ်ဆိုတာသိတယ်။
ဒီတော့ 2 ရဲ့မြှောက်ဖော်ကိန်းဘယ်လောက်ရှိသလဲသိရင်။ အလားတူပင် 5 ၏အချက်များမည်မျှရှိသည်။ ပြီးတော့ဒီဟာတွေဟာတစ်ခုချင်းစီကို product 10 နဲ့ညီအောင်ပေါင်းစပ်နိုင်မယ်လို့ပြောနိုင်တယ်။ ထို့ကြောင့်သုညတွဲစုစုပေါင်းအရေအတွက်သည်အနိမ့်ဆုံးနှင့်ညီသည်။

ယခုကျွန်ုပ်တို့သည်ဤအချက်များကို n တွင်ထည့်တွက်ရမည်။
n! = 1 * 2 * 3 ... .. * (--1) * n

ဒီတော့ 2 ကနေ n အထိကိန်းနှစ်ခုလုံးကိုထပ်ပြီးလုပ်မယ် (သူတို့ကအနည်းဆုံး ၂ လုံးပါတဲ့ကိန်းတွေဆိုတော့ 2 ကိုတိုးသွားတယ်) ။
နံပါတ်တစ်ခုစီအတွက် ၂ ကိုထပ်ကိန်းကထပ်ကိန်း ၂ နဲ့စားရင် ၂ ရဲ့ရေတွက်ခြင်းကိုရှာမယ်။
အလားတူပဲအဲ့ဒီကိန်းဂဏန်းမှာရှိတဲ့ 5 ကိုရေတွက်ရင်လည်းအတူတူပဲလုပ်ပါမယ်။
အခုကျွန်တော်တို့ဒီကိန်းနှစ်ခုထဲကအနိမ့်ဆုံးကိုပြန်ပေးလိမ့်မယ်။

ဒါကအလုပ်ဖြစ်တယ်၊ ဒါပေမယ့်ဒါကိုနည်းနည်းလောက်ပိုကောင်းအောင်လုပ်နိုင်တယ်။ ကျွန်တော်တို့မှာ 1 ကနေ n အထိကိန်းဂဏန်းတွေရှိတယ်ဆိုတာခွဲခြမ်းစိတ်ဖြာလို့ရတယ်။ ဒါဆို ၂ ရဲ့စွမ်းအားက ၅ ထက်ပိုပြီးရတယ်။
4 မတိုင်ခင်က 2 မှာ 2 က 4 အရိန်းနှစ်ခုရတယ်။ ၅ မှာပထမကိန်းကိန်းအဖြစ်ကိန်း ၅ ရမယ်။ ဒါကြောင့်ဒီအစဉ်အဆက် (တိုးပွားလာ) အရေအတွက်ကွာခြားချက်နှင့်အတူပေါ်သွားလိမ့်မယ် ဤတွင် 5 အချက်နှင့် 5 အချက်များအကြားရှိသိပ်သည်းဆကွဲပြားပုံကိုပြသသည့်သရုပ်ဖော်ပုံတစ်ခုဖြစ်သည်။

စက်ရုံ Trailing သုည Leetcode ဖြေရှင်းချက်

ထို့ကြောင့်ကျွန်ုပ်တို့သည် 2 ၏ရေတွက်သည် n အရေအတွက် 5 ထက် ပို၍ ကြီးသည်ဟုကောက်ချက်ချနိုင်သည်။
ဒါဆို ၅ ခုရဲ့အရေအတွက်ကိုရှာဖို့လိုတယ်၊ အဲဒါကပေးလိမ့်မယ်။ ဤနည်းဖြင့်ကျွန်ုပ်တို့သည်တာဝန်ကိုထက်ဝက်လျှော့ချနိုင်သည်။

စက်ရုံ Trailing သုည Leetcode ဖြေရှင်းချက်များအတွက်အကောင်အထည်ဖော်မှု

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

Java အစီအစဉ်

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

စက်ရုံ Trail သုည Leetcode ဖြေရှင်းချက်များအတွက်ရှုပ်ထွေးအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို ()) ကျွန်တော်တို့ကမြှောက်လဒ်ငါးခုလုံးကို n အထိမေ့သွားတယ်။ ကျနော်တို့ log (n) အချိန်ယူပြီးဒြပ်စင်အသီးအသီးအဘို့အပုံငါးခု၏အရေအတွက်ကိုရှာဖွေကြည့်ရှုလိမ့်မည်။ ကျွန်ုပ်တို့စစ်ဆေးခဲ့သောနံပါတ်များအများစုတွင်တစ်ခုတည်းသောအချက်ငါးခုသာရှိသောကြောင့်၎င်းသည်အို (၁) သို့ amortizes ။ ထို့ကြောင့်စုစုပေါင်းအချိန်ရှုပ်ထွေးမှုသည်အို ()) အဖြစ်ကျန်ရှိသည်။

အာကာသရှုပ်ထွေးမှု 

အို (၁) မည်သည့်အပိုမှတ်ဉာဏ်မသုံးပါ။

ချဉ်းကပ်နည်း ၂ (၅ ခု၏တွက်ချက်မှုအချက်များ)

အထက်ပါချဉ်းကပ်မှုတွင်ကျွန်ုပ်တို့သည် ၅ ၏နံပါတ်ကိုပေးထားသော n ၏အချက်အဖြစ်ရှာရန်လိုအပ်သည်ကိုတွေ့မြင်ခဲ့သည်။ အထက်ပါချဉ်းကပ်နည်းတွင်ကျွန်ုပ်တို့သည် 5 ၏မြှောက်ခြင်းများအားလုံးကို ဖြတ်၍ နံပါတ်တစ်ခုစီအတွက် ၅ ခုပေါင်းထည့်ပြီးကျွန်ုပ်တို့၏တန်ဖိုးကို linear အချိန်တွင်ရရှိခဲ့သည်။ logarithmic time အတွက် ans တွေကိုတွက်ချက်ဖို့အတွက်နောက်ဆုံးလေ့လာမှုတစ်ခုလုပ်ပါမယ်။

တည်းခိုခန်း! (ဆိုလိုသည်မှာ ၁ မှ n သို့) ကျွန်ုပ်တို့တွင် ၅ နှင့်စားလို့မရသောကိန်းဂဏန်းများရှိသည်။ (၅ အတွက်ရေတွက်ရာတွင်သုညထည့်သည်)၊ ၅ တွင်ပိုင်းခြားနိုင်သည့်နံပါတ်များရှိသည်။ ၂၅ (ဒီတစ်ကြိမ်တွင်များစွာသောကိန်းဂဏန်းတစ်ခုအပိုထပ်ဆောင်းထည့်ဝင်မှု)၊ ထို့နောက် ၁၂၅ ဖြင့်ခွဲဝေနိုင်သည်။

ထိုအခါကျွန်ုပ်တို့၏ ans သည်ဤအရာအားလုံး၏ပေါင်းလဒ်ဖြစ်လိမ့်မည်။
ဤအရာအားလုံးကိုအောက်တွင်ဖော်ပြထားသည်။
5 ရဲ့ = n / 5 + / / 25 + ၏စုစုပေါင်းအရေအတွက်က n / 125 + ။ စသည်
ပိုင်းခြေကဒီထက်နည်းသွားရင်ဒီအပိုင်းကိန်းရဲ့တန်ဖိုးကသုညဖြစ်သွားလိမ့်မယ်။

အဆင့်:
ပိုင်းခြေကို 5 နဲ့စတင်ပါ။
ပြေးပါ ကွင်းဆက်, ကြားမှာတစ် ဦး ချင်းစီအတွက်ရလဒ်မှ n / ပိုင်းခြေတန်ဖိုးကိုထည့်သွင်းခြင်းနှင့်ပိုင်းခြေ 5. အားမြှောက်ပါက loop ကိုပိုင်းခြေမရောက်မှီတိုင်အောင် <n ။

စက်ရုံ Trailing သုည Leetcode ဖြေရှင်းချက်များအတွက်အကောင်အထည်ဖော်မှု

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

Java အစီအစဉ်

#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

စက်ရုံ Trail သုည Leetcode ဖြေရှင်းချက်များအတွက်ရှုပ်ထွေးအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (မှတ်တမ်း ())) ငါတို့ကပိုင်းခြေကို n ထက်ငယ်တဲ့အထိ 5 နဲ့မြှောက်လိုက်တယ်။ ထို့ကြောင့်ကြားဖြတ်စုစုပေါင်းအရေအတွက်သည်မှတ်တမ်း (n) ဖြစ်လိမ့်မည်။

အာကာသရှုပ်ထွေးမှု 

အို (၁) မည်သည့်အပိုမှတ်ဉာဏ်မသုံးပါ။