'Coding has over 700 languages', '67% of programming jobs aren’t in the
technology industry', 'Coding is behind almost everything that is powered
by electricity'

Problem of the day

Last Updated: 17 Jan, 2021

Easy

```
The first line of the input contains a single positive integer 'T', denoting the number of test cases.
The first line of each test case contains Two space-separated positive integers 'N' and 'D', denoting the number whose square root you have to find and the number of decimal places up to which you have to find the square root.
```

```
For each test case, print a single line containing a single number denoting the square root such that the difference between the number and the actual square root is less than or equal to 10 ^ (-D).
The output of each test case will be printed in a separate line.
```

```
You don't have to print anything, it has already been taken care of. Just Implement the given function.
```

```
1 <= T <= 10 ^ 4
1 <= N <= 10 ^ 15
1 <= D <= 6
Time limit: 1 sec.
```

- We will find the integer part and decimal part of the answer separately.
- First, we will find an integral part.
- We will declare the answer variable where we will store the answer.
**Your answer could be between 1 and N so we will iterate through all the numbers from 1 to N.**- Let’s say we are currently at number i.
- If i ^ 2 = N then i is the exact answer so we will return i.
- If i ^ 2 < N then i could be a possible answer, so we will update the answer with i.
- If i ^ 2 > N then no number greater than or equal to i can be our answer so we will stop here.

- Now we have our integral part in the answer. We will now calculate its decimal part.
- We will find the answer for each decimal place separately.
- We will start with the first decimal place and we will declare an increment value 0.1.
- While our (answer + increment) ^ 2 is less than N we will keep adding an increment to the answer.
- For the second decimal place, we will declare increment with value 0.01, for the third it will be 0.001, and so on. By repeating the above approach we will find the value decimal for each of the D decimal places.

- We will return the final answer.

- We will find the integer part and decimal part of the answer separately.
- First, we will find an integral part using binary search.
**Your answer could be between 1 and N so we will use a binary search to find the answer.**- We will initialize the lower limit of binary search L with 1 and the upper limit of binary search R with min( N, 10 ^ 9 ) because the maximum value of N is 10 ^ 15 and its square root will be at max in range of 10 ^ 8.
- Declare the variable answer which we will store our integral part.
- So we will repeat the following steps until the range is greater than 0 i.e. R - L > 0.
- Declare the variable mid = (L + R) / 2.
- If mid ^ 2 = N then return mid as answer because we have found the exact answer.
- If mid ^ 2 < N
- Set the answer as mid.
- Compress the range to the right-hand side or make L = mid.

- If mid ^ 2 > N
- Compress the range to the left hand side or make R = mid.

- After a binary search, the integral part is stored in the answer.
- Now for the decimal place, we will find the answer for each decimal place separately.
- We will start with the first decimal place and we will declare an increment value of 0.1.
- While our (answer + increment)^2 is less than N we will keep adding an increment to the answer.
- For the second decimal place, we will declare increment with value 0.01, for the third, it will be 0.001, and so on. By repeating the above approach we will find the value decimal for each of the D decimal places.

- We will return the final answer.

Similar problems