UVA - 10023 - Square root

প্রবলেম বর্ননাঃ এই প্রবলেম দেওয়া আছে Y  এর স্কয়ার রুট বের করতে হবে । তবে এর রেঞ্জ দেওয়া আছে Y (1 ≤ Y ≤ 101000)  ।


সমাধান : আমি প্রথমে বাইনারী সার্চ  দিয়ে কোড টা করেছিলাম বাইনারী সার্চ  দিয়ে কিন্তু  বাইনারী সার্চ  দিয়ে এই প্রবলেম টা সলভ করা সম্ভব না প্রথমে আমি রেঞ্জটা খেয়াল  করিনি পরে প্রবলেম এ দেখলাম Y অনেক বেশি দেওয়া আছে । পরবর্তীতে আমি জাভা বিগইন্টিজার ক্লাস এর মাধ্যমে কোড টা করেছি । তবে আমি বাইনারী সার্চ দিয়ে কিভাবে স্কয়ার রুট বের করা যায় সেই কোড দিয়ে দিচ্ছি । চাইলে দেখতে পারেন।


জাভা  বিগ ইন্টিজার ক্লাস এর মাধ্যমে:

import java.util.Scanner;

import java.math.BigInteger;

public class Main {

    public static void main(String[] args) {

        Scanner input=new Scanner(System.in);

        int test=input.nextInt();

        while(test!=0){

            test--;

            BigInteger n=input.nextBigInteger();

           
            if(n.compareTo(BigInteger.ONE)==0)System.out.println(1);

            else System.out.println(sq(n));

            if(test!=0)System.out.println("");

        }

    }

    public static BigInteger sq(BigInteger n){

  

        BigInteger B=BigInteger.ZERO;

        BigInteger E=n.subtract(BigInteger.ONE);

        BigInteger M=BigInteger.ZERO;


        while(E.subtract(B).compareTo(BigInteger.ZERO)>0){

            

            M=B.add(E).divide(new BigInteger("2"));

            if(M.multiply(M).compareTo(n)==0)break;

            if(M.multiply(M).compareTo(n)>0)E=M;

            else B=M.add(BigInteger.ONE);

            //System.out.println(M+" "+M.multiply(M));

        }

        return M;

    }

}

বাইনারীসার্চ মাধ্যমে  :

#include "bits/stdc++.h"
#define ll long long
#define faster ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
ll bs(ll x)
{
    int lo=0;
    int hi=x;

    while(hi-lo>1)
    {
        int mid=(lo+hi)/2;
        if(mid*mid>=x){
            hi=mid;
        }else{
            lo=mid;
        }
    }
    if(lo>=x)return lo;
    else return hi;
}
int main ()
{

   int t;
   cin >> t;
   while(t--)
   {
       ll n;
       cin >> n;
       cout << bs(n)<<endl;
   }
   return 0;
}