Programming Interview Questions 27: Squareroot of a Number | Arden DertatArden Dertat
O(1)
- See more at: http://www.ardendertat.com/2012/01/26/programming-interview-questions-27-squareroot-of-a-number/#sthash.8EFST29l.dpuf
Logarithm of a number rounded down to the nearest integer can be calculated in constant time, by looking at the position of the leftmost 1 in the binary representation of the number. For example, the number 6 in binary is 110, and the leftmost 1 is at position 2 (starting from right counting from 0). So the logarithm of 6 rounded down is 2. This solution doesn’t always give the same result as above algorithms though, because of the rounding effects.
Read full article from Programming Interview Questions 27: Squareroot of a Number | Arden DertatArden Dertat
Find the squareroot of a given number rounded down to the nearest integer, without using the sqrt function. For example, squareroot of a number between [9, 15] should return 3, and [16, 24] should be 4.
O(LogN)
We know that the result is between 0 and N/2, so we can first try N/4 to see whether its square is less than, greater than, or equal to N. If it’s equal then we simply return that value. If it’s less, then we continue our search between N/4 and N/2. Otherwise if it’s greater, then we search between 0 and N/4. In both cases we reduce the potential range by half and continue, this is the logic of binary search. We’re not performing regular binary search though, it’s modified. We want to ensure that we stop at a number k, where k^2<=N but (k+1)^2>N. The code will clarify any doubts:
O(1)
- See more at: http://www.ardendertat.com/2012/01/26/programming-interview-questions-27-squareroot-of-a-number/#sthash.8EFST29l.dpuf
Logarithm of a number rounded down to the nearest integer can be calculated in constant time, by looking at the position of the leftmost 1 in the binary representation of the number. For example, the number 6 in binary is 110, and the leftmost 1 is at position 2 (starting from right counting from 0). So the logarithm of 6 rounded down is 2. This solution doesn’t always give the same result as above algorithms though, because of the rounding effects.
Read full article from Programming Interview Questions 27: Squareroot of a Number | Arden DertatArden Dertat
