समस्या
संख्या का वर्ग कीजिए और वर्ग के दशमलव अंकों को दो हिस्सों में काटिए: दायाँ भाग आख़िरी d अंक हैं, जहाँ d मूल संख्या के अंकों की गिनती है, और बायाँ भाग वह है जो बच जाता है (कुछ न बचे तो 0)। संख्या कापरेकर संख्या है अगर दायाँ भाग शून्य न हो और दोनों भागों का योग उसी संख्या के बराबर हो। उदाहरण के लिए, 297 में 3 अंक हैं और 297² = 88209; दायाँ भाग 209 है, बायाँ भाग 88 है, और 88 + 209 = 297। ये संख्याएँ भारतीय गणितज्ञ द. रा. कापरेकर के नाम पर हैं।
kaprekar_number(n) लिखिए।
अलग-अलग स्रोतों में परिभाषा थोड़ी अलग मिलती है। यहाँ बँटवारा हमेशा दाईं ओर से ठीक d अंकों पर होता है (यह OEIS A053816 वाला रूप है, और Wikipedia की परिभाषा में p = d वाला मामला); कुछ स्रोत दूसरी जगहों पर भी बाँटकर देखते हैं, जिससे 4879 जैसी संख्याएँ भी स्वीकार हो जाती हैं जिन्हें यह रूप अस्वीकार करता है। दाएँ भाग की शुरुआत में शून्य हो सकते हैं (703 के लिए 703² = 494209 से 494 और 209 मिलते हैं), लेकिन दायाँ भाग ख़ुद शून्य नहीं होना चाहिए, इसलिए 10, 100, ... कापरेकर संख्याएँ नहीं हैं। 1 कापरेकर संख्या है: 1² = 1 से बायाँ भाग 0 और दायाँ भाग 1 मिलता है।
इनपुट
n: जिस संख्या की जाँच करनी है।
आउटपुट
अगर ऊपर दी गई परिभाषा के अनुसार n कापरेकर संख्या है तो true लौटाइए, वरना false।
सीमाएँ
1 ≤ n ≤ 10^9
उदाहरण
इनपुट:
n = 45
अपेक्षित आउटपुट:
expected = True
इनपुट:
long long n = 45;
अपेक्षित आउटपुट:
bool expected = true;
इनपुट:
long n = 45;
अपेक्षित आउटपुट:
bool expected = true;
व्याख्या
45 में 2 अंक हैं और 45² = 2025: बायाँ भाग 20 और दायाँ भाग 25 है, और 20 + 25 = 45, इसलिए उत्तर true है।
इनपुट:
n = 4879
अपेक्षित आउटपुट:
expected = False
इनपुट:
long long n = 4879;
अपेक्षित आउटपुट:
bool expected = false;
इनपुट:
long n = 4879;
अपेक्षित आउटपुट:
bool expected = false;
व्याख्या
4879 में 4 अंक हैं और 4879² = 23804641: बायाँ भाग 2380 और दायाँ भाग 4641 है, और 2380 + 4641 = 7021, जो 4879 नहीं है, इसलिए उत्तर false है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
d को n के अंकों की गिनती मानिए और n² को 64-bit integer में रखिए।
संकेत 2
p = 10^d लेने पर दायाँ भाग n² mod p और बायाँ भाग n² / p है।
संकेत 3
अगर दायाँ भाग 0 हो तो संख्या को अस्वीकार कीजिए, भले ही योग मेल खा जाए।
अपेक्षित जटिलता
d अंकों के लिए समय O(d), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।