इस लेख में, हम किसी दी गई संख्या N के फैक्टोरियल के आधार B प्रतिनिधित्व में अनुगामी शून्यों को खोजने की समस्या को समझेंगे। उदाहरण के लिए
इनपुट: N = 7 आधार = 2 आउटपुट: 4 व्याख्या: fact(7) = 5040 बेस10 में और 1001110110000 बेस16 में जिसमें 4 अनुगामी शून्य हैं। इनपुट: N = 11 आधार = 5 आउटपुट: 2 व्याख्या: fact(11) = 39916800 बेस10 में और 40204314200 बेस16 में जिसमें 2 अनुगामी शून्य हैं।
आइए पहले किसी भी दशमलव संख्या को एक आधार से दूसरे आधार में बदलने की प्रक्रिया को दोहराते हैं। आइए (5040)10 को (?)2 में बदलने का एक उदाहरण लेते हैं
यानी संख्या को 2 से विभाजित करना और शेषफल रखना जब तक संख्या को और विभाजित न किया जा सके। परिणाम उल्टे क्रम में शेषफल होगा।
परिणामस्वरूप, हमें 4 अनुगामी शून्य मिलते हैं, और यह अनुगामी शून्य हमें तब मिला जब 2 संख्या को शेषफल 0 से विभाजित करता है।
5040 का अभाज्य गुणनखंड = 2⁴ × 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) { // अभाज्य गुणनखंड स्टोर करने के लिए फैक्टर घोषित करना // आधार के गुणनखंड में घटना के साथ। 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; // फैक्टोरियल N को विभाजित करने वाले आधार की सबसे बड़ी घात खोजना। vector < pair < int, int >> prime_factors; // primeFactorsofBase() फंक्शन द्वारा अभाज्य गुणनखंड खोजना। prime_factors = primeFactorsofBase(Base); int result = INT_MAX; for (int i = 0; i < prime_factors.size (); i++) { // न्यूनतम घात की गणना। 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); } // परिणाम में स्टोर अनुगामी शून्य प्रिंट करना। cout << "Number of trailing zeroes: " <<result; return 0; }आउटपुट
Number of trailing zeroes: 2
उपरोक्त कोड की व्याख्या
- वेक्टर का उपयोग करके आधार की सबसे बड़ी घात खोजें।
- सबसे बड़ी घात की गणना करने के लिए, वेक्टर का उपयोग करके सभी अभाज्य गुणनखंड स्टोर करें।
- फिर आधार के सभी अभाज्य गुणनखंडों की न्यूनतम घात की गणना करें।
- अंत में, परिणाम प्रिंट करें।
निष्कर्ष
इस लेख में, हमने आधार B प्रतिनिधित्व में फैक्टोरियल N के अनुगामी शून्यों की संख्या खोजने की समस्या को हल किया, जिसे हम लेगेंड्रे के सूत्र का उपयोग करके हल करते हैं। हमने उसी समस्या को हल करने के लिए C++ कोड भी लिखा। आप इस कोड को Java, C, Python आदि किसी अन्य भाषा में लिख सकते हैं। आशा है आपको यह लेख उपयोगी लगा होगा।
