Kotlin - Square Root Naïve Vs Efficient Solution Example

 It was Interview Question for Senior Developer where it was asked like 

Square root

Given an integer, we need to find the floor of its square root.

for example :

I/P = x=4

output = 2

input = x=14

output = 3

input x = 25

output = 5

I will give you 2 solutions for this problem one naive solution and another efficient solution. Let me know if anyone knows another way because to solve this type of problem we need to think of a Binary Search for an efficient solution that reduces the time complexity of the solution.

Naive Solution :

The idea is very simple we check every element one by one if it is square root then we return it.

 eg: lets dry run:

  x=9

 i = 1

 i=2

 i=3

 i=4

 result = (i-1) = 3

 So we come out of the loop when i*i greater than x which means your i-1 is the square root.

 Time Complexity is Theta of square Root of x.

 The solution in Kotlin is very very easy than core-java:

The Efficient Solution can be taken think of  Binar Search 

 So the idea we do x/2 ,x/2... if x/2 more than x then we cut the half.

  lets do the dr run:

 x =10

 low =1

 high=10

 1st Iteration:

  mid =5

 mSq=25

 high =4

  2nd Iteration:

 mid =2

 mSq=4

 low =3 , ans =2

 So Binary Search is a searching algorithm for searching an element in a sorted list or array. Binary Search is efficient than the Linear Search algorithm and performs the search operation in logarithmic time complexity for sorted arrays or lists. Binary Search performs the search operation by repeatedly dividing the search interval in half. The idea is to begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Full Code with both Naive vs Efficient Solution:

Runner. kt:

fun main() {
 println(sqRootFloor(119))
 println(sqareRootFloor(119))
}

/************Naive Solution*****/
fun sqRootFloor(x: Int): Int
{
    var i = 1
    while (i * i <= x) i++
    return i - 1
}

/*************Efficient Solution************/
fun sqareRootFloor(x: Int): Int {
    var low = 1
    var high = x
    var ans = -1
    while (low <= high) {
        val mid = (low + high) / 2
        val mSq = mid * mid
        when {
            mSq == x -> return mid
            mSq > x -> high = mid - 1
            else -> {
                low = mid + 1
                ans = mid
            }
        }
    }
    return ans
}

 Input for 4 is 2 you can simply copy-paste and test it out.

Let me know if anyone can come with a more efficient solution for this.