Sqrt (x) ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಆಪಲ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಗೂಗಲ್ ಸುಳ್ಳು ಮೈಕ್ರೋಸಾಫ್ಟ್ ಉಬರ್
ಬೈನರಿ ಹುಡುಕಾಟ ಮಠ

ಶೀರ್ಷಿಕೆ ಹೇಳುವಂತೆ, ನಾವು ಒಂದು ಸಂಖ್ಯೆಯ ವರ್ಗಮೂಲವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು. ಸಂಖ್ಯೆ ಎಂದು ಹೇಳೋಣ x, ನಂತರ Sqrt (x) ಅಂತಹ ಒಂದು ಸಂಖ್ಯೆ ಚದರ (x) * ಚದರ (x) = x. ಒಂದು ಸಂಖ್ಯೆಯ ವರ್ಗಮೂಲವು ಕೆಲವು ದಶಮಾಂಶ ಮೌಲ್ಯವಾಗಿದ್ದರೆ, ನಾವು ವರ್ಗಮೂಲದ ನೆಲದ ಮೌಲ್ಯವನ್ನು ಹಿಂದಿರುಗಿಸಬೇಕು.

ಉದಾಹರಣೆ

4
2
7
2

ಅಪ್ರೋಚ್ (ಪೂರ್ವ ನಿರ್ಮಿತ ಕಾರ್ಯಗಳು)

ದಿ ಗಣಿತ ಸಿ ++ ಮತ್ತು lang.Math ಜಾವಾ ಗ್ರಂಥಾಲಯವು ಒಂದು ಸಂಖ್ಯೆಯ ವರ್ಗಮೂಲವನ್ನು ಹಿಂದಿರುಗಿಸಲು ಪೂರ್ವ ನಿರ್ಮಿತ ಕಾರ್ಯಗಳನ್ನು ಹೊಂದಿದೆ. ನಾವು ಅರ್ಜಿ ಸಲ್ಲಿಸಬಹುದು ಮಹಡಿ () ಯಾವುದೇ ದಶಮಾಂಶ ಮೌಲ್ಯವನ್ನು ತಪ್ಪಿಸಲು.

ಕ್ರಮಾವಳಿ

  1. ಸಂಖ್ಯೆ 2 ಕ್ಕಿಂತ ಕಡಿಮೆಯಿದ್ದರೆ, ಸ್ವತಃ ಹಿಂತಿರುಗಿ
  2. ಕರೆ ಮಾಡಿ sqrt () ಕಾರ್ಯ
  3. ಪಡೆದ ಮೌಲ್ಯವನ್ನು ಮಹಡಿ
  4. ಫಲಿತಾಂಶವನ್ನು ಮುದ್ರಿಸಿ

Sqrt (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) ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಅಲ್ಗಾರಿದಮ್ನ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಲಾಗ್ಎನ್). ದಿ sqrt () ಕಾರ್ಯವು ಬಳಸುತ್ತದೆ ನ್ಯೂಟನ್-ರಾಫ್ಸನ್ O (logN) ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿರುವ ಸಂಖ್ಯೆಯ ವರ್ಗಮೂಲವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ವಿಧಾನ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (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. ಫಲಿತಾಂಶವನ್ನು ಮುದ್ರಿಸಿ

Sqrt (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) ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಅಲ್ಗಾರಿದಮ್ನ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಲಾಗ್ ಎನ್), ಬೈನರಿ ಹುಡುಕಾಟವು ಮಾದರಿ ಜಾಗವನ್ನು ಅದರ ಅರ್ಧಕ್ಕೆ ಭಾಗಿಸುತ್ತದೆ. ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, ಅದನ್ನು ಮಾಡಬಹುದು ಲಾಗ್ ಎನ್ ಹೋಲಿಕೆಗಳು.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1). ಮತ್ತೆ, ಅಸ್ಥಿರಗಳಿಗಾಗಿ ಸ್ಥಿರ ಸ್ಥಳವನ್ನು ಬಳಸಲಾಗುತ್ತದೆ.