516. Sqrt(x) with Precision (Binary Search on Float)

Given a non-negative integer x and a precision p, compute the square root of x to p decimal places. To keep the answer an exact integer, return floor(sqrt(x) * 10^p) — i.e. the digits of the square root including p decimal places, as an integer. Input: 'x, p'.

Input: 'x, p'.

Output: Integer — floor(sqrt(x) * 10^p).

Examples

Input: 2, 3
Output: 1414
Explanation: sqrt(2) ~ 1.414.

Input: 8, 4
Output: 28284
Explanation: sqrt(8) ~ 2.8284.

Input: 4, 2
Output: 200
Explanation: sqrt(4) = 2.00.

Constraints

• 0<=x<=10^9
• 0<=p<=6

Asked by