சதுரடி (x) லீட்கோட் தீர்வு  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆப்பிள் ப்ளூம்பெர்க் கூகிள் Lyft மைக்ரோசாப்ட் கிழித்து
பைனரி தேடல் குறியீட்டு பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions கணித

தலைப்பு சொல்வது போல், ஒரு எண்ணின் சதுர மூலத்தைக் கண்டுபிடிக்க வேண்டும். எண் என்று சொல்லட்டும் x, Sqrt (x) என்பது ஒரு எண் சதுர (x) * சதுர (x) = x. ஒரு எண்ணின் சதுர வேர் சில தசம மதிப்பாக இருந்தால், நாம் சதுர மூலத்தின் தரை மதிப்பை திருப்பித் தர வேண்டும்.

உதாரணமாக  

4
2
7
2

அணுகுமுறை (முன் கட்டப்பட்ட செயல்பாடுகள்)  

தி கணித சி ++ மற்றும் மொழி. கணிதம் ஜாவாவின் நூலகம் ஒரு எண்ணின் சதுர மூலத்தைத் திருப்புவதற்கு முன்பே கட்டப்பட்ட செயல்பாடுகளைக் கொண்டுள்ளது. நாங்கள் விண்ணப்பிக்கலாம் தரை() எந்த தசம மதிப்பையும் தவிர்க்க.

அல்காரிதம்

  1. எண் 2 க்கும் குறைவாக இருந்தால், தானே திரும்பவும்
  2. அழைக்கவும் sqrt () செயல்பாடு
  3. பெறப்பட்ட மதிப்பை தரையிறக்கவும்
  4. முடிவை அச்சிடுங்கள்

சதுரடி (x) லீட்கோட் தீர்வை செயல்படுத்துதல்

சி ++ திட்டம்

#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

Sqrt (x) ஐக் கண்டறிய வழிமுறையின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (logN). தி sqrt () செயல்பாடு பயன்படுத்துகிறது நியூட்டன்-ராப்சன் ஒரு எண்ணின் சதுர மூலத்தைக் கணக்கிடுவதற்கான முறை, இது O (logN) இன் நேர சிக்கலைக் கொண்டுள்ளது.

விண்வெளி சிக்கலானது

ஓ (1). மாறிகளுக்கு நிலையான இடம் பயன்படுத்தப்படுகிறது.

மேலும் காண்க
ஒரு வரிசையின் பட்டம்

அணுகுமுறை (பைனரி தேடல்)  

இங்கே, தொடங்கி எண்களின் வரம்பில் பைனரி தேடலைப் பயன்படுத்தலாம் 1 வரை செல்கிறது x / 2x = கொடுக்கப்பட்ட எண். இங்கே, பைனரி தேடலை ஒரு பதிலாக வரிசைப்படுத்தப்பட்ட வரிசையில் செயல்படுத்துகிறோம் வரிசை.

சரியான வரம்பு என அமைக்கப்பட்டுள்ளது x / 2 ஏனெனில் ஒவ்வொரு எண் x க்கும், 2 ஐ விட அதிகமாக இருந்தால், அவற்றின் சதுர மூலத்தின் தளம் x / 2 ஐ விட குறைவாக இருக்கும். பைனரி தேடலின் முடிவைப் பொறுத்து, அசல் மாதிரி இடத்தின் இடது அல்லது வலது பகுதிகளுக்கு செல்லலாம்.

சதுரடி (x)முள்

அல்காரிதம்

  1. உருவாக்கவும் பைனரிசர்ச் () சதுர (x) இன் தளம்
  2. மாறி துவக்க விடை முடிவைச் சேமிக்க
  3. எண் 2 க்கும் குறைவாக இருந்தால், தானே திரும்பவும்
  4. துவக்க விட்டு மற்றும் வலது மதிப்புகள் முறையே 1 மற்றும் x / 2
  5. வரை இடது <= வலது:
    • இந்த வரம்பின் நடுவில் கண்டுபிடிக்கவும், நடு = இடது + வலது / 2
    • நடுப்பகுதியில் சதுரம் சமமாக இருந்தால் x,  இது சதுர மூலமாக இருப்பதால் அதைத் திருப்பி விடுங்கள்
    • நடுப்பகுதியில் சதுரம் குறைவாக இருந்தால் x, இடது = நடுப்பகுதி + 1 அமைப்பதன் மூலம் வலது பாதியில் செல்லவும்
    • இல்லையெனில், வலது = நடுப்பகுதி 1 ஐ அமைப்பதன் மூலம் இடது பாதியில் குதித்து இந்த மதிப்பை சேமிக்கவும் விடை
  6. முடிவை அச்சிடுங்கள்

சதுரடி (x) லீட்கோட் தீர்வை செயல்படுத்துதல்

சி ++ திட்டம்

#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

Sqrt (x) ஐக் கண்டறிய வழிமுறையின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (logN), பைனரி தேடல் மாதிரி இடத்தை அதன் பாதியாகப் பிரிக்கிறது. மோசமான நிலையில், அது வரை செய்ய முடியும் logN ஒப்பீடுகள்.

மேலும் காண்க
வரிசைகளைப் பயன்படுத்தி அடுக்கு செயல்படுத்தவும்

விண்வெளி சிக்கலானது

ஓ (1). மீண்டும், மாறிகளுக்கு நிலையான இடம் பயன்படுத்தப்படுகிறது.