ফ্যাক্টরিয়াল ট্রেলিং জিরো লেটকোড সলিউশন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় ব্লুমবার্গ
ম্যাথ

সমস্যা বিবৃতি

এই সমস্যায় আমাদের খুঁজে বের করতে হবে যে এনে কতগুলি পিছনে জিরো থাকবে!
ইনপুট হিসাবে দেওয়া

5 এর মতো একটিও পিছনে শূন্য!
5! = 5 * 4 * 3 * 2 * 1 = 120

উদাহরণ

n = 3
0

ব্যাখ্যা: 3! = 6, কোনও পিছনে শূন্য নয়

n = 0
0

ব্যাখ্যা: 0! = 1, কোনও পিছনে শূন্য নয়

 

এনে ট্রেলিং শূন্যের সংখ্যাটি সন্ধান করতে! , একটি সহজ উপায় এন গণনা করা হয়! এবং শেষে কত জিরো আছে তা পরীক্ষা করুন। এটি কেবলমাত্র 10 দ্বারা সংখ্যাকে ভাগ করে নেওয়া যায় কিনা তা যাচাই করে আমরা কেবল 0 টি বাকী পেয়েছি এবং তারপরে শেষ শূন্যটি 10 ​​দিয়ে বিভাজন করে মুছে ফেলতে পারলে আমরা প্রতিবার শূন্যের সমান বাকী না হওয়া পর্যন্ত আমরা এটি গণনা করতে পারি।

তবে এই পদ্ধতিটি সহজ পূর্ণসংখ্যার সাথে ব্যবহারিক নয় কারণ আমরা জানি! একটি খুব বড় সংখ্যা। সি ++ এবং জাভাতে সাধারণ পূর্ণসংখ্যার আকার সর্বোপরি 64৪-বিট যা কেবলমাত্র একটি পূর্ণসংখ্যা 2 ^ 63 - 1. এর সীমাতে সঞ্চয় করতে পারে যা 10 ^ 18 এর কাছাকাছি। জাভাতে আমরা বড় বড় সংখ্যা এন এর মতো সংরক্ষণ করতে বিগইন্টিজার ক্লাস ব্যবহার করতে পারি। তবে এই নিষ্ঠুর বলের পদ্ধতির বড় সময় এবং স্থান জটিলতা রয়েছে।

এখানে আমরা এন এর পিছনে শূন্যগুলি খুঁজে বের করার জন্য কার্যকর সমাধান আলোচনা করতে যাচ্ছি!

পন্থা 1 (5 এর গুণনীয় কারণ)

আমরা বলতে পারি যে পিছনে থাকা শূন্যগুলির মোট সংখ্যা 10 এর সংখ্যার কত গুণ তার গুণনের সমান হবে। এবং আমরা জানি যে প্রতি 10 টি দুটি প্রধান সংখ্যা 2 এবং 5 এর সাথে গঠিত of
সুতরাং যদি আমরা খুঁজে বের করি যে সংখ্যায় 2 এর কতগুলি কারণ রয়েছে। একইভাবে 5 এর কতগুলি কারণ রয়েছে। তারপরে আমরা বলতে পারি যে এগুলির প্রত্যেকটি 10 ​​টির সমান পণ্য তৈরি করতে একত্রিত হবে Therefore সুতরাং মোট চলমান শূন্যের সংখ্যা ন্যূনতম (2 এর গণনা, 5 এর গণনা) সমান হবে।

এখন আমাদের এই বিষয়গুলি এনতে গণনা করতে হবে!
এন! = 1 * 2 * 3… .. * (এন -1) * এন

সুতরাং আমরা 2 থেকে এন থেকে সমস্ত সংখ্যার উপর পুনরাবৃত্তি করব (2 দ্বারা বৃদ্ধি কারণ তারা কমপক্ষে একটি 2 এর সমন্বিত সংখ্যাগুলি) one
প্রতিটি সংখ্যার জন্য আমরা বারবার এটি 2 দিয়ে বিভক্ত করব যতক্ষণ না এটি 2 দ্বারা বিভাজ্য হয় সেই সংখ্যার গুণককরণের ক্ষেত্রে 2 এর গণনাটি সন্ধান করতে।
একইভাবে 5 সংখ্যার গণনাটি খুঁজতে আমরা একই কাজ করব।
এখন আমরা এই দুটি গণনার মধ্যে সর্বনিম্ন ফিরিয়ে দেব।

এটি কাজ করে তবে আমরা এটিকে কিছুটা অনুকূলও করতে পারি can আমরা বিশ্লেষণ করতে পারি যে আমাদের 1 থেকে এন পর্যন্ত সংখ্যা রয়েছে, তাই আমরা সর্বদা 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

ফ্যাক্টরিয়াল ট্রেলিং জিরো লেটকোড সলিউশন এর জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু) : আমরা এন পর্যন্ত পাঁচটির সমস্ত গুণকের উপরে পুনরাবৃত্তি করছি। এটি পাঁচটি সংখ্যা গণনা করার জন্য আমরা লগ (এন) সময় নিচ্ছি এমন প্রতিটি উপাদানের মতো দেখতে। তবে এটি হে (1) এর সাথে অ্যামোরোটাইজ হয়েছে কারণ আমরা যে সংখ্যক সংখ্যক চেক করেছি তার মধ্যে পাঁচটিতে কেবলমাত্র একক উপাদান রয়েছে। সুতরাং মোট সময়ের জটিলতা ও (এন) হিসাবে রয়ে গেছে।

স্পেস জটিলতা ity 

ও (1): কোনও অতিরিক্ত মেমরি ব্যবহার করা হয় না।

অ্যাপ্রোচ 2 (দক্ষতার সাথে 5 টি গুণনের গুণক)

উপরের পদ্ধতির মধ্যে আমরা দেখেছি যে কেবলমাত্র প্রদত্ত এন এর ফ্যাক্টর হিসাবে আমাদের 5 এর গণনা খুঁজে পাওয়া দরকার! উপরের পদ্ধতির মধ্যে আমরা 5 টির সমস্ত গুণককে ছাপিয়েছি এবং প্রতিটি সংখ্যার জন্য 5 এর গণনা যুক্ত করেছি এবং রৈখিক সময়ে আমাদের উত্তরগুলি পেয়েছি। আমরা একটি চূড়ান্ত পর্যবেক্ষণ করব যা আমাদের লগারিদমিক সময়ে উত্তরগুলি গণনা করার অনুমতি দেবে।

সরাইখানা! (অর্থাত্ 1 থেকে এন) আমাদের কিছু সংখ্যা রয়েছে যা 5 দ্বারা বিভাজ্য নয় (0 এর গণনার জন্য 5 অবদান), তারপরে আমাদের কিছু সংখ্যা রয়েছে যা 5 দ্বারা বিভাজ্য হয় (প্রতিটি একটি গণনা করে), তারপরে আমাদের এমন সংখ্যা রয়েছে যা দ্বারা বিভাজ্য 25 (এবার এই বহু সংখ্যার থেকে একটি অতিরিক্ত অবদান), তারপরে 125 দ্বারা বিভাজ্য (এগুলির মধ্যে একটি অতিরিক্ত অবদান), এর মতো এবং আরও।

তাহলে আমাদের উত্তরগুলি এই সমস্ত অবদানের যোগফল হবে।
আমরা নীচে হিসাবে এই সমস্ত সংক্ষিপ্ত করতে পারেন:
5 এর = এন / 5 + এন / 25 + এন / 125 + এর মোট গণনা। শীঘ্রই
ডোনমিনেটর n এর চেয়ে কম হওয়া পর্যন্ত এটি যাবে কারণ ভগ্নাংশের অবিচ্ছেদ্য মান শূন্যের পরে।

পদক্ষেপ:
5 দিয়ে ডিনমিনেটর ভেরিয়েবল শুরু করুন।
একটি চালান লুপ, প্রতিটি পুনরাবৃত্তিতে ফলাফলের জন্য n / ডিনোমিনেটর মান যুক্ত করুন এবং ডিনোমিনেটরকে 5 দ্বারা গুণ করুন den

ফ্যাক্টরিয়াল ট্রেলিং জিরো লেটকোড সলিউশন এর বাস্তবায়ন

সি ++ প্রোগ্রাম

#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

ফ্যাক্টরিয়াল ট্রেলিং জিরো লেটকোড সলিউশন এর জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (লগ (এন)): এটি এন এর চেয়ে কম না হওয়া পর্যন্ত আমরা প্রতিবার 5 দ্বারা গুণক করছি। সুতরাং পুনরাবৃত্তির মোট সংখ্যা লগ (এন) হবে।

স্পেস জটিলতা ity 

ও (1): কোনও অতিরিক্ত মেমরি ব্যবহার করা হয় না।