Square root (decimal)

Easy
0/40
Average time to solve is 10m
profile
Contributed by
23 upvotes
Asked in companies
UberVisaFacebook

Problem statement

You have been given two integers 'N' and 'D', Your task is to find the square root of the number 'N' with precision up to 'D' decimal places i.e. the difference between your answer and the correct answer should be less than 10 ^ (-D).

For example if N = 10 and D = 3, then your answer will be 3.162.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
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.
Output Format: 
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.
Note: 
You don't have to print anything, it has already been taken care of. Just Implement the given function.
Constraints: 
1 <= T <= 10 ^ 4
1 <= N <= 10 ^ 15
1 <= D <= 6

Time limit: 1 sec.
Sample Input 1 :
2
1 6
10 3
Sample Output 1:
1.000000
3.162
Explanation to sample Input 1:
In the first test case the actual square root of 1 is 1.000000 and the answer is 1 so the difference between actual square root and the output is 0.000000 which is less than 10 ^ (-6) or 0.000001 .

In the second case the actual square root of 10 is 3.162277 and the output is  3.162 so the difference between the actual square root and the output is 0.000277 which is less than 10^(-3) or 0.001 .
Sample input 2 :
2
12 6
20 1
Sample Output 2:
3.464101
4.4
Explanation to sample Input 2:
In the first test case the actual square root of 12 is 3.464101 and the output is 3.464101 so the difference between the actual square root and the output is 0.000000 which is less than or equal to 10^(-6) or 0.000001 .

In the first test case the actual square root of 20 is 4.472135 and the output is 4.4 so the difference between the actual square root and the output is 0.072135 which is less than 10^(-1) or 0.1 .
Hint

Check for all numbers using brute force.

Approaches (2)
Bruteforce
  • 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.
Time Complexity

O(sqrt(N)) where ‘N’ is the number that you want to find the square root of.

 

As we are traversing through all the number 1 to sqrt of ‘N’, the overall complexity is O(sqrt(N)).

Space Complexity

O(1).

 

Since we are using constant extra memory.

Code Solution
(100% EXP penalty)
Square root (decimal)
Full screen
Console