चौरस (एक्स) लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन सफरचंद ब्लूमबर्ग Google लिफ्ट मायक्रोसॉफ्ट उबेर
बायनरी शोध गणित

शीर्षक म्हटल्याप्रमाणे आम्हाला संख्येचे वर्गमूल शोधणे आवश्यक आहे. समजा संख्या आहे x, तर Sqrt (x) ही अशी एक संख्या आहे चौरस (x) * चौरस (x) = x. जर एखाद्या संख्येचे वर्गमूल काही दशांश मूल्य असेल तर आपल्याला चौरस मूळचे फर्श मूल्य परत करावे लागेल.

उदाहरण

4
2
7
2

दृष्टीकोन (पूर्वनिर्मित कार्ये)

अगोदर निर्देश केलेल्या बाबीसंबंधी बोलताना गणित सी ++ ची लायब्ररी lang.Math जावाच्या लायब्ररीमध्ये अंकांचे वर्गमूल परत करण्यासाठी पूर्वनिर्मित कार्ये असतात. आम्ही अर्ज करू शकतो मजला () कोणत्याही दशांश मूल्य टाळण्यासाठी.

अल्गोरिदम

  1. जर संख्या 2 पेक्षा कमी असेल तर स्वतः परत या
  2. कॉल करा चौरस () कार्य
  3. मिळविलेले मूल्य मजला करा
  4. निकाल प्रिंट करा

चौरस (एक्स) लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

int mySqrt(int x)
{
    if(x <= 1)
        return x;
    return floor(sqrt(x));
}

int main()
{
    int x = 7;
    cout << mySqrt(x) << '\n';
}

जावा कार्यक्रम

import java.lang.Math;

class sqrt_x
{
    static int mySqrt(int x)
    {
        if(x <= 1)
            return x;
        return (int)Math.floor(Math.sqrt(x));
    }

    public static void main(String args[])
    {
        int x = 7;
        System.out.println(mySqrt(x));
    }
}
2

एसक्यूआरटी (एक्स) शोधण्यासाठी अल्गोरिदमचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (लॉगएन) अगोदर निर्देश केलेल्या बाबीसंबंधी बोलताना चौरस () फंक्शन वापरते न्यूटन-रॅफसन संख्येच्या वर्गमूलची गणना करण्याची पद्धत, ज्यामध्ये ओ (लॉगएन) ची वेळ अवघड असते.

जागेची जटिलता

ओ (1). चल साठी सतत जागा वापरली जाते.

दृष्टीकोन (बायनरी शोध)

येथे, आम्ही प्रारंभ होणार्‍या संख्येच्या श्रेणीवर बायनरी शोध लागू करू शकतो 1 पर्यंत जात आहे x / 2जेथे x = दिलेली संख्या. येथे, आम्ही बाईयरी शोध एका ऐवजी निवडलेल्या क्रमवारी लावलेल्या क्रमावर लागू करतो अॅरे.

उजवी मर्यादा म्हणून सेट केली गेली आहे x / 2 कारण प्रत्येक x साठी, 2 पेक्षा जास्त, त्यांच्या चौरस रूटची मजला x / 2 पेक्षा कमी असेल. बायनरी शोधाच्या परिणामावर, आम्ही मूळ नमुना असलेल्या डाव्या किंवा उजव्या अर्ध्या भागावर जाऊ शकतो.

चौरस (x)

अल्गोरिदम

  1. तयार बायनरी शोध () फूट रिटर्न फ्लोअर स्क्वेअर (एक्स)
  2. चल प्रारंभ करा उत्तर परिणाम संग्रहित करण्यासाठी
  3. जर संख्या 2 पेक्षा कमी असेल तर स्वतः परत या
  4. आरंभ करा बाकी आणि योग्य अनुक्रमे 1 आणि x / 2 म्हणून मूल्ये
  5. पर्यंत डावीकडे <= उजवीकडे:
    • या श्रेणीचे मध्य शोधा, मध्य = डावीकडे + उजवीकडे / 2
    • जर मध्यम चौरस बरोबर असेल x,  हे वर्गमूळ आहे म्हणून परत करा
    • मध्यभागी चौरस पेक्षा कमी असल्यास x, डावे = मध्य +1 सेट करून उजवीकडे अर्ध्यावर जा
    • अन्यथा, उजवा = मध्य - 1 सेट करून डावीकडे अर्ध्यावर जा आणि हे मूल्य मध्ये जतन करा उत्तर
  6. निकाल प्रिंट करा

चौरस (एक्स) लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int x)
{
    int left = 1 , right = x / 2 , mid , ans;
    long temp;

    while(left <= right)
    {
        mid = (left + (right - left) / 2);
        temp = (long)mid * (long)mid;
        //mid * mid can be large, so use long
        if(temp == x)
            return mid;
        if(temp < x)
            ans = mid , left = mid + 1;
        else
            right = mid - 1;
    }
    return ans;
}

int mySqrt(int x)
{
    if(x <= 1)
        return x;
    return binarySearch(x);
}


int main()
{
    int x = 7;
    cout << mySqrt(x) << '\n';
}

जावा कार्यक्रम

import java.lang.Math;

class sqrt_x
{
    static int binarySearch(int x)
    {
        int left = 1 , right = x / 2 , mid , ans = 0;
        long temp;

        while(left <= right)
        {
            mid = (left + (right - left) / 2);
            temp = (long)mid * (long)mid;
            //mid * mid can be large, so use long
            if(temp == x)
                return mid;
            if(temp < x)
            {
                ans = mid;
                left = mid + 1;
            }
            else
                right = mid - 1;
        }
        return ans;
    }

    static int mySqrt(int x)
    {
        if(x <= 1)
            return x;
        return binarySearch(x);
    }

    public static void main(String args[])
    {
        int x = 7;
        System.out.println(mySqrt(x));
    }
}
2

एसक्यूआरटी (एक्स) शोधण्यासाठी अल्गोरिदमचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (लॉगएन), बायनरी शोध नमुना जागा त्याच्या अर्ध्या भागावर ठेवत आहे. सर्वात वाईट परिस्थितीत, हे अप करू शकते लॉगएन तुलना.

जागेची जटिलता

ओ (1). पुन्हा, चल करीता स्थिर जागा वापरली जाते.