समस्या
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
उदाहरण
इनपुट:
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 है।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।