ചതുരശ്ര (x) ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് ഗൂഗിൾ ലിഫ്റ്റ് മൈക്രോസോഫ്റ്റ് യൂബർ
ബൈനറി തിരയൽ മഠം

ശീർഷകം പറയുന്നതുപോലെ, ഒരു സംഖ്യയുടെ വർ‌ഗ്ഗ റൂട്ട് കണ്ടെത്തേണ്ടതുണ്ട്. നമ്പർ ആണെന്ന് പറയട്ടെ x, Sqrt (x) അത്തരത്തിലുള്ള ഒരു സംഖ്യയാണ് ചതുരശ്ര (x) * ചതുരശ്ര (x) = x. ഒരു സംഖ്യയുടെ വർ‌ഗ്ഗ റൂട്ട് കുറച്ച് ദശാംശ മൂല്യമാണെങ്കിൽ‌, ഞങ്ങൾ‌ സ്‌ക്വയർ‌ റൂട്ടിന്റെ ഫ്ലോർ‌ മൂല്യം തിരികെ നൽകണം.

ഉദാഹരണം

4
2
7
2

സമീപനം (മുൻകൂട്ടി നിർമ്മിച്ച പ്രവർത്തനങ്ങൾ)

ദി കണക്ക് സി ++ ന്റെ ലൈബ്രറി lang.Math ഒരു സംഖ്യയുടെ വർ‌ഗ്ഗ റൂട്ട് നൽ‌കുന്നതിന് മുൻ‌കൂട്ടി നിർമ്മിച്ച ഫംഗ്ഷനുകൾ‌ ജാവയുടെ ലൈബ്രറിയിലുണ്ട്. ഞങ്ങൾക്ക് അപേക്ഷിക്കാം ഫ്ലോർ () ഏതെങ്കിലും ദശാംശ മൂല്യം ഒഴിവാക്കാൻ.

അൽഗോരിതം

  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) കണ്ടെത്തുന്നതിന് അൽഗോരിത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (logN). ദി sqrt () ഫംഗ്ഷൻ ഉപയോഗിക്കുന്നു ന്യൂട്ടൺ-റാപ്‌സൺ O (logN) ന്റെ സമയ സങ്കീർ‌ണ്ണതയുള്ള ഒരു സംഖ്യയുടെ വർ‌ഗ്ഗ റൂട്ട് കണക്കാക്കാനുള്ള രീതി.

സ്ഥല സങ്കീർണ്ണത

O (1). വേരിയബിളുകൾക്കായി സ്ഥിരമായ ഇടം ഉപയോഗിക്കുന്നു.

സമീപനം (ബൈനറി തിരയൽ)

ഇവിടെ നിന്ന് ആരംഭിക്കുന്ന സംഖ്യകളുടെ ശ്രേണിയിൽ നമുക്ക് ബൈനറി തിരയൽ പ്രയോഗിക്കാൻ കഴിയും 1 വരെ പോകുന്നു x / 2ഇവിടെ x = നൽകിയ നമ്പർ. ഇവിടെ, ഒരു എന്നതിന് പകരം തിരഞ്ഞെടുത്ത അടുക്കിയ ശ്രേണിയിൽ ഞങ്ങൾ ബൈനറി തിരയൽ നടപ്പിലാക്കുന്നു ശ്രേണി.

ശരിയായ പരിധി ഇതായി സജ്ജമാക്കി 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

ചതുരശ്ര (x) കണ്ടെത്തുന്നതിന് അൽഗോരിത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (logN), ബൈനറി തിരയൽ സാമ്പിൾ സ്ഥലത്തെ അതിന്റെ പകുതിയായി വിഭജിക്കുന്നു. ഏറ്റവും മോശം അവസ്ഥയിൽ, അതിന് കഴിയും ലോഗ് എൻ താരതമ്യങ്ങൾ.

സ്ഥല സങ്കീർണ്ണത

O (1). വീണ്ടും, വേരിയബിളുകൾക്കായി സ്ഥിരമായ ഇടം ഉപയോഗിക്കുന്നു.