class Solution {
public:
    int bs(int x)
    {
        
        int long long n=x/2;
        int long long s=0, e=n;
        int long long mid=s+(e-s)/2;
        int long long ans=0;
        while(s<=e)
        {
            int long long p=mid*mid;
            int long long p2=(mid+1)*(mid+1);
            if(p<=x&&p2>x) return mid;
            if(p<x) 
            {
                ans=
                s=mid+1;
            }
            else e=mid-1;
            mid=s+(e-s)/2;
        }
        return mid;
    }
    
    int mySqrt(int x) {
        if(x==0) return 0;
        if(x==1||x==2||x==3) return 1;
        int ans=bs(x);
        return ans;
    }
 };