आधार B में अनुगामी शून्यों की संख्या ज्ञात कीजिए जो N का प्रतिनिधित्व करते हैं! सी ++ का उपयोग करना

इस लेख में, हम किसी दी गई संख्या N के अनुगामी शून्य को उसके भाज्य के आधार B निरूपण में खोजने की समस्या को समझेंगे। उदाहरण के लिए

Input : N = 7 Base = 2
Output : 4
Explanation : fact(7) = 5040 in base10 and 1001110110000 in base16 having 4 trailing zero.

Input : N = 11 Base = 5
Output : 2
Explanation : fact(11) = 39916800 in base10 and 40204314200 in base16 having 2 trailing zeroes.

आइए सबसे पहले किसी भी दशमलव संख्या को एक आधार से दूसरे आधार में बदलने की प्रक्रिया का पुनरावलोकन करें। आइए (5040)10 को (?)2

यानी, संख्या को 2 से विभाजित करना और शेष को तब तक रखना जब तक कि संख्या को और विभाजित न किया जा सके। परिणाम शेष उल्टे क्रम में होगा।

परिणामस्वरूप, हमारे पास 4 अनुगामी शून्य हैं, और यह अनुगामी शून्य हमें तब प्राप्त होता है जब 2 संख्या को शेषफल से विभाजित करता है।

5040 =24 * 56711 * 3381 * 181 का अभाज्य गुणनखंडन अर्थात 2 को 5040 को 4 बार विभाजित करने पर शेष 0 होता है जो अनुगामी शून्य के बराबर होता है। इस तरह, हम अनुगामी शून्यों की संख्या की गणना कर सकते हैं।

समाधान खोजने के लिए दृष्टिकोण

अनुगामी शून्यों की संख्या ज्ञात करने के तरीके के बारे में हमने ऊपर चर्चा की। हमें भाज्य N में B की उच्चतम घात ज्ञात करने की आवश्यकता है, मान लीजिए कि आधार B =14 है, तो आधार 14 में 14 को 10 के रूप में दर्शाया जाएगा, अर्थात (14)10 =(10)14। इसे लीजेंड्रे के सूत्र के रूप में भी जाना जाता है।

उपरोक्त दृष्टिकोण के लिए C++ कोड

यहां C++ सिंटैक्स दिया गया है जिसे हम दी गई समस्या को हल करने के लिए इनपुट के रूप में उपयोग कर सकते हैं -

उदाहरण

#include <bits/stdc++.h>
using namespace std;

vector < pair < int, int >> primeFactorsofBase(int Base) {
   // declaring factors to store prime factors
   // along with occurence in factorisation of Base .
   vector < pair < int, int >>factors;

   for (int i = 2; Base != 1; i++) {
      if (Base % i == 0) {
         int count = 0;
         while (Base % i == 0){
            Base = Base / i;
            count++;
         }

         factors.push_back (make_pair (i, count));
      }
   }
   return factors;
}


int main () {
   int N = 11, Base = 5;
   // finding the largest power of Base that divides factorial N.
   vector < pair < int, int >>prime_factors;
   // finding prime factors by primeFactorsofBase() function.
   prime_factors = primeFactorsofBase(Base);

   int result = INT_MAX;
   for (int i = 0; i < prime_factors.size (); i++) {
      // calculating minimum power.
      int count = 0;
      int r = prime_factors[i].first;
      while (r <= N){
         count += (N / r);
         r = r * prime_factors[i].first;
      }
      result = min (result, count / prime_factors[i].second);
   }
   //printing trailing zeroes stored in result.
   cout << "Number of trailing zeroes: " <<result;
   return 0;
}

आउटपुट

Number of trailing zeroes: 2

उपरोक्त कोड की व्याख्या

• वेक्टर का उपयोग करके आधार की सबसे बड़ी शक्ति का पता लगाएं।
• सबसे बड़ी शक्ति की गणना करने के लिए, सभी प्रमुख कारकों को संग्रहीत करने के लिए वैक्टर का उपयोग करके प्रमुख कारकों की गणना करें।
• फिर आधार के सभी अभाज्य गुणनखंडों की न्यूनतम शक्ति की गणना करें।
• अंत में, परिणाम प्रिंट करना।

निष्कर्ष

इस लेख में, हम फैक्टोरियल एन के आधार बी प्रतिनिधित्व में अनुगामी शून्यों की संख्या खोजने की समस्या को हल करते हैं, जिसे हम लीजेंड्रे के सूत्र का उपयोग करके हल करते हैं। हम उसी समस्या को हल करने के लिए C++ कोड भी लिखते हैं। आप इस कोड को किसी अन्य भाषा जैसे जावा, सी, पायथन, आदि में लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।