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

पूर्णांक वर्गमूल

वर्गमूल function के बिना वह सबसे बड़ी पूर्ण संख्या खोजिए जिसका वर्ग n से ज़्यादा न हो।

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

  • Binary search से उत्तर की रेंज में खोज करना
  • Overflow के बिना r × r की तुलना n से करना
  • Floating point की rounding ग़लतियों से बचना

समस्या

n का पूर्णांक वर्गमूल (integer square root) उसका वह वर्गमूल है जिसे नीचे की ओर पूर्णांक में बदल दिया गया हो, यानी वह सबसे बड़ा पूर्णांक r जिसके लिए r × r ≤ n हो। लाइब्रेरी के वर्गमूल function floating point संख्याओं पर काम करते हैं और बड़े इनपुट पर एक से चूक सकते हैं। इसलिए इसे सिर्फ़ पूर्णांकों से निकालिए, जैसे संभावित उत्तरों पर binary search करके।

integer_square_root(n) लिखिए।

इनपुट

n: एक ऋणेतर (non-negative) पूर्णांक।

आउटपुट

वह सबसे बड़ा पूर्णांक r लौटाइए जिसके लिए r × r ≤ n हो।

सीमाएँ

0 ≤ n ≤ 10^18

उदाहरण

उदाहरण 1
इनपुट:
n = 50

अपेक्षित आउटपुट:
expected = 7
इनपुट:
long long n = 50;

अपेक्षित आउटपुट:
long long expected = 7;
इनपुट:
long n = 50;

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

व्याख्या

7 × 7 = 49 ≤ 50 है, लेकिन 8 × 8 = 64 > 50, इसलिए उत्तर 7 है।

उदाहरण 2
इनपुट:
n = 144

अपेक्षित आउटपुट:
expected = 12
इनपुट:
long long n = 144;

अपेक्षित आउटपुट:
long long expected = 12;
इनपुट:
long n = 144;

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

व्याख्या

144 ठीक 12 × 12 है, इसलिए उत्तर 12 है।

कैसे हल करें

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

संकेत 1

उत्तर 0 और n के बीच है, और r बढ़ने पर r × r भी बढ़ता है, इसलिए आप हर कदम पर रेंज आधी कर सकते हैं।

संकेत 2

बड़े n के लिए r × r overflow हो सकता है; इसकी जगह r की तुलना n / r से कीजिए, या ऊपरी सीमा को सीमित रखिए।

संकेत 3

0, 1 और 3 जैसे छोटे इनपुट हाथ से जाँचकर देखिए।

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

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

संदर्भ

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

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

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

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

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

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