ਸਕੁਐਰਟੀ (ਐਕਸ) ਲੀਟਕੋਡ ਹੱਲ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਸੇਬ ਬਲੂਮਬਰਗ ਗੂਗਲ ਲਿੱਟ Microsoft ਦੇ ਉਬੇਰ
ਬਾਈਨਰੀ ਖੋਜ ਗਣਿਤ

ਜਿਵੇਂ ਕਿ ਸਿਰਲੇਖ ਕਹਿੰਦਾ ਹੈ, ਸਾਨੂੰ ਇੱਕ ਸੰਖਿਆ ਦਾ ਵਰਗ ਵਰਗ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਦੱਸ ਦੇਈਏ ਕਿ ਨੰਬਰ ਹੈ x, ਫਿਰ ਵਰਗ (ਐਕਸ) ਇਕ ਅਜਿਹਾ ਨੰਬਰ ਹੈ ਵਰਗ (x) * ਵਰਗ (x) = x. ਜੇ ਕਿਸੇ ਸੰਖਿਆ ਦਾ ਵਰਗ ਵਰਗ ਕੁਝ ਦਸ਼ਮਲਵ ਦਾ ਮੁੱਲ ਹੁੰਦਾ ਹੈ, ਤਾਂ ਸਾਨੂੰ ਵਰਗ ਰੂਟ ਦਾ ਫਲੋਰ ਮੁੱਲ ਵਾਪਸ ਕਰਨਾ ਹੋਵੇਗਾ.

ਉਦਾਹਰਨ

4
2
7
2

ਪਹੁੰਚ (ਪ੍ਰੀ-ਬਿਲਟ ਫੰਕਸ਼ਨ)

The ਗਣਿਤ C ++ ਅਤੇ ਲਾਇਬ੍ਰੇਰੀ 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

ਸਕੁਐਰਟ (ਐਕਸ) ਨੂੰ ਲੱਭਣ ਲਈ ਐਲਗੋਰਿਦਮ ਦਾ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਲੌਗ ਐਨ) The ਵਰਗ () ਫੰਕਸ਼ਨ ਨਿtonਟਨ-ਰੈਫਸਨ ਇੱਕ ਸੰਖਿਆ ਦੇ ਵਰਗ ਰੂਟ ਦੀ ਗਣਨਾ ਕਰਨ ਲਈ methodੰਗ, ਜਿਸ ਵਿੱਚ O (logN) ਦੀ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਹੁੰਦੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1). ਵੇਰੀਏਬਲਸ ਲਈ ਨਿਰੰਤਰ ਸਪੇਸ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਜਾਂਦੀ ਹੈ.

ਪਹੁੰਚ (ਬਾਈਨਰੀ ਖੋਜ)

ਇੱਥੇ, ਅਸੀਂ ਸ਼ੁਰੂ ਹੋ ਰਹੇ ਨੰਬਰਾਂ ਦੀ ਇੱਕ ਸੀਮਾ ਤੇ ਬਾਈਨਰੀ ਖੋਜ ਲਾਗੂ ਕਰ ਸਕਦੇ ਹਾਂ 1 ਤੱਕ ਜਾ ਰਿਹਾ x / 2ਜਿਥੇ x = ਦਿੱਤੀ ਗਈ ਨੰਬਰ. ਇੱਥੇ, ਅਸੀਂ ਬਾਈ ਦੀ ਬਜਾਏ ਚੁਣੇ ਹੋਏ ਕ੍ਰਮਬੱਧ ਕ੍ਰਮ ਤੇ ਬਾਈਨਰੀ ਖੋਜ ਨੂੰ ਲਾਗੂ ਕਰਦੇ ਹਾਂ ਐਰੇ.

ਸਹੀ ਸੀਮਾ ਦੇ ਤੌਰ ਤੇ ਸੈੱਟ ਕੀਤਾ ਗਿਆ ਹੈ x / 2 ਕਿਉਂਕਿ ਹਰ ਨੰਬਰ x ਲਈ, 2 ਤੋਂ ਵੱਧ, ਉਨ੍ਹਾਂ ਦੇ ਵਰਗ ਰੂਟ ਦੀ ਫਰਸ਼ x / 2 ਤੋਂ ਘੱਟ ਹੋਵੇਗੀ. ਬਾਈਨਰੀ ਖੋਜ ਦੇ ਨਤੀਜਿਆਂ ਦੇ ਅਧਾਰ ਤੇ, ਅਸੀਂ ਮੂਲ ਨਮੂਨੇ ਵਾਲੀ ਥਾਂ ਦੇ ਖੱਬੇ ਜਾਂ ਸੱਜੇ ਅੱਧ 'ਤੇ ਜਾ ਸਕਦੇ ਹਾਂ.

ਵਰਗ (ਐਕਸ)

ਐਲਗੋਰਿਥਮ

  1. ਇੱਕ ਬਣਾਓ ਬਾਈਨਰੀ ਖੋਜ () ਫੰਕਸ਼ਨ ਰਿਟਰਨਿੰਗ ਫਲੋਰ sqrt (x)
  2. ਪਰਿਵਰਤਨ ਅਰੰਭ ਕਰੋ ans ਨਤੀਜੇ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ
  3. ਜੇ ਨੰਬਰ 2 ਤੋਂ ਘੱਟ ਹੈ, ਤਾਂ ਆਪਣੇ ਆਪ ਵਾਪਸ ਜਾਓ
  4. ਅਰੰਭ ਕਰੋ ਨੂੰ ਛੱਡ ਅਤੇ ਸੱਜੇ ਕ੍ਰਮਵਾਰ 1 ਅਤੇ x / 2 ਦੇ ਤੌਰ ਤੇ ਮੁੱਲ
  5. ਜਦ ਤੱਕ ਖੱਬੇ <= ਸੱਜੇ:
    • ਇਸ ਸੀਮਾ ਦੇ ਵਿਚਕਾਰ ਲੱਭੋ, ਵਿਚਕਾਰ = ਖੱਬੇ + ਸੱਜੇ / 2
    • ਜੇ ਅੱਧ ਦਾ ਵਰਗ ਬਰਾਬਰ ਹੈ x,  ਇਸਨੂੰ ਵਾਪਸ ਕਰੋ ਜਿਵੇਂ ਕਿ ਇਹ ਵਰਗ ਰੂਟ ਹੈ
    • ਜੇ ਅੱਧ ਦਾ ਵਰਗ ਘੱਟ ਹੈ x, ਖੱਬੇ = ਅੱਧ + 1 ਸੈਟ ਕਰਕੇ ਸੱਜੇ ਅੱਧ 'ਤੇ ਜਾਓ
    • ਨਹੀਂ ਤਾਂ, ਸੱਜੇ = ਅੱਧ - 1 ਨੂੰ ਸੈਟ ਕਰਕੇ ਖੱਬੇ ਅੱਧ 'ਤੇ ਜਾਓ ਅਤੇ ਇਸ ਮੁੱਲ ਨੂੰ ਵਿੱਚ ਸੁਰੱਖਿਅਤ ਕਰੋ ans
  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). ਫੇਰ, ਵੇਰੀਏਬਲਸ ਲਈ ਨਿਰੰਤਰ ਜਗ੍ਹਾ ਵਰਤੀ ਜਾਂਦੀ ਹੈ.