सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

मॉड्यूलर घातांक

तेज़ घातांक विधि से base की घात exponent को किसी संख्या के modulo में निकालिए।

आप क्या सीखेंगे

  • O(log exponent) कदमों में किसी संख्या की बहुत बड़ी घात निकालना
  • overflow से बचने के लिए हर बीच के मान को छोटा रखना
  • exponent 0 और modulus 1 को संभालना

समस्या

base^exponent mod modulus निकालिए। exponent 10^18 तक हो सकता है, इसलिए base से उतनी बार गुणा करना असंभव है; इसकी बजाय वर्ग करके घात निकालने की विधि (exponentiation by squaring) अपनाइए: exponent के बाइनरी अंकों को देखिए, हर कदम पर आधार का वर्ग कीजिए, और जब अंक 1 हो तो उसे परिणाम में गुणा कर दीजिए। यहाँ के किसी भी exponent के लिए इसमें लगभग 60 कदम लगते हैं।

modular_exponentiation(base, exponent, modulus) लिखिए।

शुरुआत में ही base को modulus के modulo में छोटा कर लीजिए, और हर गुणा के बाद भी। चूँकि modulus ≤ 10^9 है, ऐसे दो छोटे किए गए मानों का गुणनफल 10^18 से कम रहता है और signed 64-bit integer में आ जाता है।

इनपुट

base: आधार।

exponent: वह घात जिस तक आधार को उठाना है।

modulus: वह संख्या जिससे शेषफल लेना है।

आउटपुट

base^exponent mod modulus लौटाइए, जो 0 से modulus − 1 तक का कोई मान होगा। हर base के लिए base^0 को 1 मानिए, 0 के लिए भी, इसलिए exponent 0 होने पर उत्तर 1 mod modulus है।

सीमाएँ

0 ≤ base ≤ 10^18

0 ≤ exponent ≤ 10^18

1 ≤ modulus ≤ 10^9

उदाहरण

उदाहरण 1
इनपुट:
base = 3
exponent = 13
modulus = 50

अपेक्षित आउटपुट:
expected = 23
इनपुट:
long long base = 3;
long long exponent = 13;
long long modulus = 50;

अपेक्षित आउटपुट:
long long expected = 23;
इनपुट:
long base = 3;
long exponent = 13;
long modulus = 50;

अपेक्षित आउटपुट:
long expected = 23;

व्याख्या

3^13 = 1,594,323, और 1,594,323 = 50 × 31,886 + 23, इसलिए उत्तर 23 है।

उदाहरण 2
इनपुट:
base = 2
exponent = 10
modulus = 1000

अपेक्षित आउटपुट:
expected = 24
इनपुट:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;

अपेक्षित आउटपुट:
long long expected = 24;
इनपुट:
long base = 2;
long exponent = 10;
long modulus = 1000;

अपेक्षित आउटपुट:
long expected = 24;

व्याख्या

2^10 = 1024, और 1024 mod 1000 = 24।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

exponent को सबसे निचले बिट से शुरू करके एक-एक बाइनरी अंक करके देखिए।

संकेत 2

हर कदम पर आधार का वर्ग कीजिए, और जब मौजूदा बिट 1 हो तो उसे परिणाम में गुणा कीजिए।

संकेत 3

परिणाम को 1 % modulus से शुरू कीजिए, ताकि modulus 1 होने पर उत्तर 0 आए।

अपेक्षित जटिलता

समय O(log exponent), अतिरिक्त स्थान O(1)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।