ਫੈਕਟਰੀਅਲ ਟ੍ਰੇਲਿੰਗ ਜ਼ੀਰੋਜ਼ ਲੀਟਕੋਡ ਹੱਲ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਬਲੂਮਬਰਗ
ਗਣਿਤ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਇਸ ਸਮੱਸਿਆ ਵਿਚ ਸਾਨੂੰ ਇਹ ਪਤਾ ਲਗਾਉਣਾ ਹੋਵੇਗਾ ਕਿ ਐਨ ਵਿਚ ਕਿੰਨੇ ਪਛੜੇ ਜ਼ੀਰੋ ਹੋਣਗੇ!
ਇੰਪੁੱਟ ਦੇ ਤੌਰ ਤੇ ਦਿੱਤਾ ਗਿਆ ਹੈ.

ਜਿਵੇਂ ਕਿ 5 ਵਿੱਚ ਇੱਕ ਪਿਛਲੀ ਜ਼ੀਰੋ ਹੈ!
5! = 5 * 4 * 3 * 2 * 1 = 120

ਉਦਾਹਰਨ

n = 3
0

ਵਿਆਖਿਆ: 3! = 6, ਕੋਈ ਪਿਛਲਾ ਜ਼ੀਰੋ ਨਹੀਂ

n = 0
0

ਵਿਆਖਿਆ: 0! = 1, ਕੋਈ ਪਿਛਲਾ ਜ਼ੀਰੋ ਨਹੀਂ

 

ਐਨ ਵਿਚ ਪਛੜੇ ਜ਼ੀਰੋ ਦੀ ਗਿਣਤੀ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ! , ਇੱਕ ਸਧਾਰਣ ਤਰੀਕਾ ਹੈ n ਦੀ ਗਣਨਾ ਕਰਨਾ! ਅਤੇ ਵੇਖੋ ਕਿ ਅੰਤ ਵਿੱਚ ਕਿੰਨੇ ਜ਼ੀਰੋ ਹਨ. ਇਹ ਅਸੀਂ ਸਿਰਫ ਇਹ ਪਤਾ ਲਗਾ ਕੇ ਕਰ ਸਕਦੇ ਹਾਂ ਕਿ ਕੀ ਗਿਣਤੀ ਨੂੰ 10 ਨਾਲ ਵੰਡਣਾ ਹੈ ਤਾਂ ਅਸੀਂ ਬਾਕੀ ਰਹਿੰਦੇ 0 ਪ੍ਰਾਪਤ ਕਰਦੇ ਹਾਂ ਅਤੇ ਫਿਰ ਆਖਰੀ ਜ਼ੀਰੋ ਨੂੰ 10 ਨਾਲ ਵੰਡ ਕੇ ਹਟਾ ਸਕਦੇ ਹਾਂ. ਅਸੀਂ ਇਸ ਨੂੰ ਉਦੋਂ ਤਕ ਗਿਣ ਸਕਦੇ ਹਾਂ ਜਦ ਤੱਕ ਕਿ ਹਰ ਵਾਰ ਜ਼ੀਰੋ ਦੇ ਬਰਾਬਰ ਨਹੀਂ ਮਿਲਦਾ.

ਪਰ ਇਹ ਪਹੁੰਚ ਸਧਾਰਣ ਪੂਰਨ ਅੰਕ ਦੇ ਨਾਲ ਵਿਹਾਰਕ ਨਹੀਂ ਹੈ ਕਿਉਂਕਿ ਅਸੀਂ ਜਾਣਦੇ ਹਾਂ ਐਨ! ਇੱਕ ਬਹੁਤ ਵੱਡੀ ਗਿਣਤੀ ਹੈ. ਸੀ ++ ਅਤੇ ਜਾਵਾ ਵਿਚ ਸਧਾਰਣ ਪੂਰਨ ਅੰਕ ਦਾ ਆਕਾਰ ਵਧੀਆ 64 2-ਬਿੱਟ ਹੁੰਦਾ ਹੈ ਜੋ ਸਿਰਫ ਇਕ ਪੂਰਨ ਅੰਕ ਨੂੰ ^ - of - of ਦੀ ਸੀਮਾ ਵਿਚ ਸਟੋਰ ਕਰ ਸਕਦਾ ਹੈ ਜੋ ਕਿ ਤਕਰੀਬਨ 63 ^ 1 ਹੈ. ਜਾਵਾ ਵਿਚ ਅਸੀਂ ਵੱਡੀ ਗਿਣਤੀ ਵਿਚ n ਵਰਗੇ ਸਟੋਰ ਕਰਨ ਲਈ ਬਿਗਇੰਟੇਜ਼ਰ ਕਲਾਸ ਦੀ ਵਰਤੋਂ ਕਰ ਸਕਦੇ ਹਾਂ. ਲੇਕਿਨ ਇਹ ਜ਼ਾਲਮ ਫੋਰਸ ਪਹੁੰਚ ਵਿਚ ਬਹੁਤ ਵੱਡਾ ਸਮਾਂ ਅਤੇ ਸਥਾਨ ਦੀ ਗੁੰਝਲਤਾ ਹੈ.

ਇੱਥੇ ਅਸੀਂ ਐਨ ਵਿਚ ਪਛੜੇ ਜ਼ੀਰੋ ਨੂੰ ਲੱਭਣ ਲਈ ਕੁਸ਼ਲ ਹੱਲ ਬਾਰੇ ਵਿਚਾਰ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ!

ਪਹੁੰਚ 1 (5 ਦੇ ਕਾਰਕ ਗਿਣਨ ਵਾਲੇ)

ਅਸੀਂ ਕਹਿ ਸਕਦੇ ਹਾਂ ਕਿ ਪਿੱਛੇ ਜਾਣ ਵਾਲੇ ਜ਼ੀਰੋ ਦੀ ਕੁੱਲ ਗਿਣਤੀ 10 ਦੀ ਗਿਣਤੀ ਦੇ ਬਰਾਬਰ ਹੋਵੇਗੀ ਕਿ ਕਿੰਨੀ ਵਾਰ 10 ਉਸ ਸੰਖਿਆ ਦਾ ਕਾਰਕ ਹੈ. ਅਤੇ ਅਸੀਂ ਜਾਣਦੇ ਹਾਂ ਕਿ ਹਰ 2 ਦੋ ਮੁੱਖ ਨੰਬਰ 5 ਅਤੇ XNUMX ਦੇ ਉਤਪਾਦ ਦਾ ਬਣਿਆ ਹੈ.
ਇਸ ਲਈ ਜੇ ਸਾਨੂੰ ਪਤਾ ਚਲਦਾ ਹੈ ਕਿ ਸੰਖਿਆ ਵਿਚ 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 ਕਾਰਕਾਂ ਵਿਚਕਾਰ ਘਣਤਾ ਕਿਵੇਂ ਵੱਖਰੀ ਹੈ.

ਫੈਕਟਰੀਅਲ ਟ੍ਰੇਲਿੰਗ ਜ਼ੀਰੋਜ਼ ਲੀਟਕੋਡ ਹੱਲ

ਇਸ ਲਈ ਅਸੀਂ ਇਹ ਸਿੱਟਾ ਕੱ can ਸਕਦੇ ਹਾਂ ਕਿ 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

ਫੈਕਟਰੀਅਲ ਟਰੇਲਿੰਗ ਜ਼ੀਰੋਜ਼ ਲੀਟਕੋਡ ਹੱਲ ਲਈ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ): ਅਸੀਂ ਐਨ ਤਕ ਪੰਜ ਦੇ ਸਾਰੇ ਗੁਣਾਂ ਨੂੰ ਦੁਹਰਾਉਂਦੇ ਹਾਂ. ਇਹ ਹਰੇਕ ਤੱਤ ਦੀ ਤਰ੍ਹਾਂ ਜਾਪ ਸਕਦਾ ਹੈ ਕਿ ਅਸੀਂ ਪੰਜ ਦੀ ਗਿਣਤੀ ਨੂੰ ਲੱਭਣ ਲਈ ਲੌਗ (ਐਨ) ਸਮਾਂ ਲੈ ਰਹੇ ਹਾਂ. ਪਰ ਇਹ ਓ (1) ਨੂੰ ਅਮੋਰਟਾਈਜ਼ ਕਰਦਾ ਹੈ ਕਿਉਂਕਿ ਵੱਡੀ ਗਿਣਤੀ ਵਿਚ ਜੋ ਅਸੀਂ ਚੈਕ ਕੀਤੇ ਹਨ, ਵਿਚ ਕੇਵਲ ਪੰਜ ਦਾ ਇਕੋ ਕਾਰਕ ਹੁੰਦਾ ਹੈ. ਇਸ ਲਈ ਕੁੱਲ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਓ (ਐਨ) ਦੇ ਤੌਰ ਤੇ ਰਹਿੰਦੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ 

ਓ (1): ਕੋਈ ਵਾਧੂ ਮੈਮੋਰੀ ਨਹੀਂ ਵਰਤੀ ਜਾਂਦੀ.

ਪਹੁੰਚ 2 (ਕੁਸ਼ਲਤਾ ਨਾਲ 5 ਦੇ ਗਿਣਤੀ ਕਰਨ ਵਾਲੇ ਕਾਰਕ)

ਉਪਰੋਕਤ ਪਹੁੰਚ ਵਿਚ ਅਸੀਂ ਵੇਖਿਆ ਕਿ ਸਾਨੂੰ 5 ਦੀ ਗਿਣਤੀ ਨੂੰ ਸਿਰਫ ਦਿੱਤੇ ਐੱਨ ਦੇ ਕਾਰਕ ਵਜੋਂ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ !. ਉਪਰੋਕਤ ਪਹੁੰਚ ਵਿੱਚ ਅਸੀਂ 5 ਦੇ ਸਾਰੇ ਗੁਣਾਂ ਨੂੰ ਘਟਾ ਦਿੱਤਾ ਹੈ ਅਤੇ ਹਰੇਕ ਨੰਬਰ ਲਈ 5 ਦੀ ਗਿਣਤੀ ਸ਼ਾਮਲ ਕੀਤੀ ਹੈ ਅਤੇ ਲੰਬੇ ਸਮੇਂ ਵਿੱਚ ਸਾਡੇ ਜਵਾਬ ਪ੍ਰਾਪਤ ਕੀਤੇ. ਅਸੀਂ ਇੱਕ ਅੰਤਮ ਨਿਰੀਖਣ ਕਰਾਂਗੇ ਜੋ ਸਾਨੂੰ ਲਾਗੀਰਥਿਕ ਸਮੇਂ ਵਿੱਚ ਉੱਤਰਾਂ ਦੀ ਗਣਨਾ ਕਰਨ ਦੀ ਆਗਿਆ ਦੇਵੇਗਾ.

ਵਿਚ ਐਨ! (ਭਾਵ 1 ਤੋਂ n ਤੱਕ) ਸਾਡੇ ਕੋਲ ਕੁਝ ਸੰਖਿਆਵਾਂ ਹਨ ਜੋ 5 ਦੁਆਰਾ ਵਿਭਾਜਨ ਯੋਗ ਨਹੀਂ ਹਨ (0 ਦੀ ਗਿਣਤੀ ਲਈ 5 ਦਾ ਯੋਗਦਾਨ), ਫਿਰ ਸਾਡੇ ਕੋਲ ਕੁਝ ਸੰਖਿਆਵਾਂ ਹਨ ਜੋ 5 ਦੁਆਰਾ ਵੰਡੀਆਂ ਜਾ ਸਕਦੀਆਂ ਹਨ (ਹਰੇਕ ਇੱਕ ਯੋਗਦਾਨ) 25 (ਇਸ ਵਾਰ ਇਨ੍ਹਾਂ ਬਹੁਤ ਸਾਰੀਆਂ ਸੰਖਿਆਵਾਂ ਵਿਚੋਂ ਇਕ ਵਾਧੂ ਯੋਗਦਾਨ), ਫਿਰ 125 ਦੁਆਰਾ ਵੰਡਿਆ ਜਾ ਸਕਦਾ ਹੈ (ਇਹਨਾਂ ਵਿਚੋਂ ਇਕ ਵਾਧੂ ਯੋਗਦਾਨ), ਇਸ ਤਰ੍ਹਾਂ ਅਤੇ ਹੋਰ.

ਤਦ ਸਾਡੇ ਉੱਤਰ ਇਨ੍ਹਾਂ ਸਾਰੇ ਯੋਗਦਾਨਾਂ ਦਾ ਜੋੜ ਹੋਣਗੇ.
ਅਸੀਂ ਇਨ੍ਹਾਂ ਸਾਰਿਆਂ ਦਾ ਸੰਖੇਪ ਹੇਠ ਲਿਖ ਸਕਦੇ ਹਾਂ:
5 ਦੀ = n / 5 + n / 25 + n / 125 + ਦੀ ਕੁੱਲ ਗਿਣਤੀ. ਇਸ ਤਰਾਂ
ਇਹ ਉਦੋਂ ਤਕ ਜਾਰੀ ਰਹੇਗਾ ਜਦੋਂ ਤੱਕ ਹਰ ਤੱਤ n ਤੋਂ ਘੱਟ ਨਹੀਂ ਹੁੰਦਾ, ਕਿਉਂਕਿ ਉਸ ਤੋਂ ਬਾਅਦ ਭਾਗ ਦਾ ਅਟੁੱਟ ਮੁੱਲ ਜ਼ੀਰੋ ਹੋ ਜਾਵੇਗਾ.

ਕਦਮ:
ਡੋਮੋਨੀਏਟਰ ਵੇਰੀਏਬਲ 5 ਨਾਲ ਅਰੰਭ ਕਰੋ.
ਏ ਚਲਾਓ ਲੂਪ, ਹਰੇਕ ਦੁਹਰਾਓ ਵਿੱਚ ਨਤੀਜੇ ਵਜੋਂ n / denominator ਮੁੱਲ ਸ਼ਾਮਲ ਕਰੋ ਅਤੇ ਹਰ ਨੂੰ 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): ਕੋਈ ਵਾਧੂ ਮੈਮੋਰੀ ਨਹੀਂ ਵਰਤੀ ਜਾਂਦੀ.