වර්ග (x) ලීට්කෝඩ් විසඳුම  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ගූගල් ලයිෆ්ට් මයික්රොසොෆ්ට් Uber
ඇල්ගොරිතම ද්විමය සෙවීම කේතීකරණය සම්මුඛ පරීක්ෂණ සම්මුඛ සාකච්ඡා ලීට්කෝඩ් LeetCodeSolutions ගණිතය

මාතෘකාව පවසන පරිදි, අපි සංඛ්‍යාවක වර්ගමූලය සොයාගත යුතුය. අංකය යැයි කියමු x, Sqrt (x) යනු එවැනි අංකයකි වර්ග (x) * වර්ග (x) = x. සංඛ්‍යාවක වර්ග මූලය යම් දශම අගයක් නම්, අපට වර්ග මූලයේ බිම් අගය ආපසු ලබා දිය යුතුය.

උදාහරණයක්  

4
2
7
2

ප්‍රවේශය (පෙර සාදන ලද කාර්යයන්)  

එම ගණිත C ++ සහ භාෂාව. ගණිතය ජාවා පුස්තකාලයට සංඛ්‍යාවක වර්ග මූලය ආපසු ලබා දීම සඳහා කලින් සාදන ලද කාර්යයන් ඇත. අපට අයදුම් කළ හැකිය මහල() කිසිදු දශම අගයක් වළක්වා ගැනීමට.

ඇල්ගොරිතම

  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

වර්ග (x) සොයා ගැනීම සඳහා ඇල්ගොරිතමයේ සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (ලොග්එන්). එම sqrt () ශ්‍රිතය භාවිතා කරයි නිව්ටන්-රැප්සන් O (logN) හි කාල සංකීර්ණත්වයක් ඇති සංඛ්‍යාවක වර්ග මූල ගණනය කිරීමේ ක්‍රමය.

අවකාශයේ සංකීර්ණතාව

ඕ (1). විචල්යයන් සඳහා නියත අවකාශය භාවිතා වේ.

මෙයද බලන්න
අරාව පිළිබඳ උපාධිය

ප්‍රවේශය (ද්විමය සෙවීම)  

මෙන්න, අපට ආරම්භ වන සංඛ්‍යා පරාසයක ද්විමය සෙවීම යෙදිය හැකිය 1 දක්වා යනවා x / 2x = දී ඇති අංකය. මෙන්න, අපි ද්විමය සෙවීම a වෙනුවට තෝරාගත් වර්ග කළ අනුක්‍රමයක් මත ක්‍රියාත්මක කරමු අරාව.

නිවැරදි සීමාව ලෙස සකසා ඇත x / 2 සෑම අංක x ටම 2 ට වඩා වැඩි නම් ඒවායේ වර්ග මූලයේ බිම x / 2 ට වඩා අඩු වනු ඇත. ද්විමය සෙවුමේ ප්‍රති result ලය අනුව අපට මුල් නියැදි අවකාශයේ වම් හෝ දකුණු අර්ධයට පනින්න පුළුවන්.

වර්ග (x)පින්

ඇල්ගොරිතම

  1. සාදන්න ද්විමය සෙවීම () වර්ග අඩි (x) හි ආපසු එන තට්ටුව
  2. විචල්‍යය ආරම්භ කරන්න හොඳින් සලකලා ප්‍රති .ලය ගබඩා කිරීමට
  3. අංකය 2 ට වඩා අඩු නම්, නැවත පැමිණෙන්න
  4. ආරම්භ කරන්න වම් සහ අයිතිය අගයන් පිළිවෙලින් 1 සහ x / 2 ලෙස
  5. තුරු වමේ <= දකුණ:
    • මෙම පරාසය මැද සොයා ගන්න, mid = වමේ + දකුණ / 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

වර්ග (x) සොයා ගැනීම සඳහා ඇල්ගොරිතමයේ සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (ලොග්එන්), ද්විමය සෙවුම නියැදි අවකාශය එහි භාගයට බෙදමින් සිටින නිසා. නරකම අවස්ථාවක, එය කළ හැකිය logN සැසඳීම්.

මෙයද බලන්න
පෝලිම් භාවිතයෙන් තොගය ක්‍රියාත්මක කරන්න

අවකාශයේ සංකීර්ණතාව

ඕ (1). නැවතත්, විචල්යයන් සඳහා නියත අවකාශය භාවිතා වේ.