आसान 0 हल किए गए 0% स्वीकृति

Integer Square Root

Find the largest whole number whose square does not exceed n, without a square root function.

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

  • Search an answer range with binary search
  • Compare r × r with n without overflowing
  • Avoid floating point rounding errors

समस्या

अनुवाद दिखाएँ

The integer square root of n is the square root rounded down: the largest integer r with r × r ≤ n. Library square roots work on floating point numbers and can be off by one for large inputs, so compute it with integers only, for example with a binary search over possible answers.

Implement integer_square_root(n).

Input

n: A non-negative integer.

Output

Return the largest integer r such that 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 but 8 × 8 = 64 > 50, so the answer is 7.

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

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

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

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

व्याख्या

144 is exactly 12 × 12, so the answer is 12.

कैसे हल करें

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

संकेत 1

The answer lies between 0 and n, and r × r grows as r grows, so you can halve the range each step.

संकेत 2

For large n, r × r can overflow; compare r with n / r instead, or cap the upper bound.

संकेत 3

Check small inputs like 0, 1 and 3 by hand.

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

O(log n) time, O(1) extra space

संदर्भ

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

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

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

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

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

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