Square root without a library function
Coding problemEasy-MediumAsked in: Accolite, Amazon, Flipkart, Microsoft, VMware
Given a list of non-negative integers, return the square root of each one rounded down: the largest whole number whose square is at most that number. Keep the order of the list. Do not use a library square root or power function.
A number can be as large as 9 times 10 to the 18th and the list can hold 1,000 numbers, so counting up one number at a time is too slow, and squaring a large guess can overflow a 64-bit integer.
Examples
Example 1
Input: xs = [8,16,0]
Output: [2,4,0]
2 x 2 = 4 is at most 8, but 3 x 3 = 9 is not.
Example 2
Input: xs = [1,2,3]
Output: [1,1,1]
Example 3
Input: xs = []
Output: []
Constraints
- The list holds between 0 and 1,000 numbers
- Each number is between 0 and 9,000,000,000,000,000,000
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.